if statement for every possibility

2 views (last 30 days)
Grayson Ransom
Grayson Ransom on 19 Jan 2022
Edited: John D'Errico on 20 Jan 2022
% my "if subsetsum~=i" should only display if every subsetsum~=i,
Any help on how to make this work? I am trying to find all weird numbers.
n=10:99;
for i=n
factors=divisors(i);
factorArray=factors(1:end-1);
lengthArray=length(factorArray);
if sum(factorArray,2)>i
for j=3:lengthArray
subsetsum=sum(nchoosek(factorArray,j),2);
if subsetsum~=i
disp(i)
end
end
end
end
  2 Comments
Grayson Ransom
Grayson Ransom on 20 Jan 2022
@John D'Errico im trying to find all weird numbers. so an interger x whos divisors D={d_1,...d_n} where x is not in D. and the sum of D>x and any subset of D does not sum to equal x

Sign in to comment.

Accepted Answer

_
_ on 20 Jan 2022
Edited: _ on 20 Jan 2022
n = 10:99;
weird_numbers = [];
for i = n
factors = divisors(i);
factorArray = factors(1:end-1);
lengthArray = length(factorArray);
if sum(factorArray) > i
is_weird = true;
for j = 3:lengthArray
subsetsum = sum(nchoosek(factorArray,j),2);
if any(subsetsum == i)
is_weird = false;
end
end
if is_weird
weird_numbers(end+1) = i;
end
end
end
disp(weird_numbers);
70
  1 Comment
Grayson Ransom
Grayson Ransom on 20 Jan 2022
thank you very much I see exactly what was going wrong. I really appreciate it.

Sign in to comment.

More Answers (1)

John D'Errico
John D'Errico on 20 Jan 2022
Edited: John D'Errico on 20 Jan 2022
Ok. Let me see if I understand. A wierd number x is a positive integer, such that given the set of proper divisors of x (that is, not including x itself) no subset of the divisors of x can sum to x? Ah. You also require that the sum of the proper divisors of x is greater than x.
Can you give an example of one such number? I can probably find one online. But I am way too lazy. :)
Hmm. Is a perfect number a wierd number? That is, 6 and 28 are perfect numbers, the two I can think of offhand. The divisors of 6 are {1,2,3}. So any perfect number cannot be wierd, since the sum of all the divisors is exactly the number itself by definition of a perfect number.
Conversely, all prime numbers are also not wierd, by that definition. A prime number has only one proper divisor, i.e., the number 1. Therefore, no prime number can possibly be wierd.
In fact, you need abundant numbers, which are themselves fairly uncommon. An abundant number is one where the sum of the proper divisors is greater than the sum of the number itself.
In there, I see the statement that the first 28 abundant numbers are...
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, ... (sequence A005101 in the OEIS).
That is one of the sequences you can find in the OEIS, a truly great site. :) Check it out!
Sometime in the past, I wrote the alldivisors code. I've attached it to this answer.
n = 12;
D = setdiff(alldivisors(n),n)
D =
1 2 3 4 6
sum(D)
ans =
16
As you can see, alldivisors returns the set of all divisors, which includes the number itself, so setdiff excludes the number. And there we see that 12 is indeed abundant. However, 12 is not in fact wierd, I think, becase a proper subset of those divisors sums to 12. That is, 12 = 1 + 2 + 3 + 6.
Anyway, a simple scheme to search for wierd numbers would be to first find abundant numbers. Only then would you look to see if a proper subset of the numbers exists that sums to n itself.
By the way, one quick conjecture is that all abundant numbers are even, but that will prove to be false, since 945 is both abundant and odd. It is known to be the smallest odd abundant number.
How would I do that test? At first glance, I would probably use intlinprog, ONCE I find an abundant number. But now I notice I could use my partitions code. It is on the file exchange, but it is not the best tools for this problem. Anyway, my initial code would look vaguely like...
AbundantList = [];
WierdList = [];
N = 2;
while N < 1e5
N = N + 1;
D = setdiff(alldivisors(N),N);
if sum(D) > N
% N is abundant...
AbundantList(end+1) = N;
% does any proper subset of those divisors yield A itself?
% this is arguably a job for a binary integer programming code. But perhaps my
% function partitions will work as well.
if isempty(partitions(N,D,1))
% At this point, we already know N is abundant. If no partition of N
% exists, based on that divisor set, then N is also wierd
WierdList(end + 1) = N;
end
end
end
I stopped the code when it got as far out as N = 420, because it was too slow.
AbundantList
AbundantList =
Columns 1 through 22
12 18 20 24 30 36 40 42 48 54 56 60 66 70 72 78 80 84 88 90 96 100
Columns 23 through 44
102 104 108 112 114 120 126 132 138 140 144 150 156 160 162 168 174 176 180 186 192 196
Columns 45 through 66
198 200 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282
Columns 67 through 88
288 294 300 304 306 308 312 318 320 324 330 336 340 342 348 350 352 354 360 364 366 368
Columns 89 through 101
372 378 380 384 390 392 396 400 402 408 414 416 420
WierdList
WierdList =
70
So the first Wierd number it found, and the only one found up to 420 is 70.
setdiff(alldivisors(70),70)
ans =
1 2 5 7 10 14 35
The code I wrote above using partitions (partitions is on the file exchange) is too CPU intensive though. I'd need to rewrite it using a better test for Wierdness, perhaps intlinprog. So is 70 truly a wierd number? We van verify that, perhaps using a quickie little function I just wrote:
function S = allsums(V);
% computes all distinct partial sums of the elements of the (integer) vector V
% S = allsums(V)
%
% Arguments:
% V - an integer vector. may be a row or column vector. No test is done
% that V is integer, and the code will still run, but non-integer
% elements may result in tiny differences between partial sums produced,
% on the order of machine epsilon. These will not be recognised as being
% the same thing.
%
% S - Vector of unique partial sums of the elements of V. S will be
% sorted in increasing order. 0 will be included in that set, as the sum
% of no elements, thus the empty partial subset of V.
n = numel(V);
S = 0;
for i = 1:numel(V)
S = unique([S,S+V(i)]);
end
I'll try it out now with the divisors of 70.
allsums([1 2 5 7 10 14 35])
ans =
Columns 1 through 22
0 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Columns 23 through 44
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
Columns 45 through 66
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Columns 67 through 73
67 68 69 71 72 73 74
As you can see, there are no partial sums that yield 70. So 70 is indeed the smallest wierd number. To see if there are larger wierd numbers, we can now use the allsums code itself. Or, I can go back and write a binary integer programming call to intlinprog. But allsums is reasonably fast, at least for smaller problems.
tic,
WierdList = [];
N = 2;
while N < 25000
N = N + 1;
D = setdiff(alldivisors(N),N);
if sum(D) > N
AbundantList(end+1) = N;
% N is abundant, but is it wierd?
if ~ismember(N,allsums(D))
% We now know that N is wierd.
WierdList(end + 1) = N;
end
end
end
toc
That code is actually pretty fast. It took my computer only 9 seconds to find the first 46 wierd numbers.
WierdList
WierdList =
Columns 1 through 11
70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990
Columns 12 through 22
11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610
Columns 23 through 33
15890 16030 16310 16730 16870 17272 17570 17990 18410 18830 18970
Columns 34 through 44
19390 19670 19810 20510 21490 21770 21910 22190 23170 23590 24290
Columns 45 through 46
24430 24710
Having now written the above codes, I'll look online to see what is said about wierd numbers...
There it is. I knew I'd find something if I looked. And in that link, I find this line, again referencing the OEIS of course:
70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, 13790, 13930, 14770, ... (sequence A006037 in the OEIS).
It looks like my code is now at least decent, but not very good. Could I write better code? Certainly, yes. I can always improve code, though the odds are good that to make significant improvements, I would need to choose better algorithms. I would probably need to improve the way I accumulate the list, since the incrementally growing array I have there is a BAD thing. It will slow down the code if the list gets too long. There are tools to fix that problem too though. In fact, I've written serval codes that also live oon the file exchange. A search for growdata will find them.
Finally, just for kicks, are there any odd numbers in that list? And even though there were 54 odd abundant numbers found below 25000, none of them were wierd.
find(mod(WierdList,2))
ans =
1×0 empty double row vector
Again, some quick reading is better than infinitely much testing on my part. The Wiki page tells me that no odd wierd numbers are known, that are less than 1e21. I would need to write far better code of course to look that far. And since this is your project, I'll stop now, on a problem where I should probably not have done as much as I did.

Products


Release

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!