Problems & Puzzles: Puzzles

Puzzle 233. A little twist

Les Reid has posed another interesting puzzle in the "Challenge" section of his site. His puzzle goes like his:

Find the earliest two solutions for numbers n such that the sum of the proper divisors of n are greater than n and no subset of these divisors sums up to n.

As I told you, the problem is interesting but - in my humble opinion -  not particularly hard to solve. As a matter of fact the earliest solution can be obtained without using a computer once you devise the appropriate approach.

So I will make a little twist(*) to it, in order to make this puzzle a bit harder, I guess...

Questions:

1. Can you make a clever/interesting/useful characterization of the odd numbers n  such that the sum of their proper divisors are greater than n? 

2. Find the earliest solution for odd numbers n such that  the sum of the proper divisors of n are greater than n and no subset of these divisors sums up to n; or demonstrate that such solutions do not exist.

_____

(*) I hope that Les Reid take this frequent by me posing other side of his always interesting puzzles as a sign of my admiration for his extremely good taste for the beauty puzzles.


Solution:

Luke Pebody, Jud Mc Cranie, Faride Firoozbakht and Wilfred Whiteside sent different contributions to this puzzle that after the little twist turned to be a big and old problem (sorry folks)...

***

Luke Pebody wrote the minimalist following message "Problem Two is very difficult: http://mathworld.wolfram.com/WeirdNumber.html".

Enough to remind to me the B2 section of the R. K. Guy well known book (UPiNT), pp. 45-53. Here we learn that the numbers asked in the original Les Reid's puzzle are called "abundant but not pseudo perfect" or also "weird" after Benkoski.

My little twist to the Reid's puzzle just turned to ask for "odd-weird numbers", for which now I know that no one single example is known (is every odd abundant number pseudo perfect? = is every weird number even?)

***

Jud wrote "these numbers are called Weird Numbers. There are no known odd ones" and added the reference for the EIS sequence A006037.

***

Faride has proved that you can find abundant numbers lacking of any quantity of consecutive prime numbers from 3 to p. For example the earliest abundant squarefree number not divided by 3 is 33426748355. The earliest abundant squarefree number not divided by 3 & 5 is 1357656019974967471687377449, and so on.

She has more results about abundant odd numbers that will be shown in a few days. These results hopefully may be of some help in tackling the question 2 of this puzzle.

***

Wilfred Whiteside found that this problem was considered by the great Erdos and you can get $10.00 of his funds if you get just one weird odd number (not necessarily the earliest as we asked here). At the end he suggest in which direction might we work in seeking a solution for these numbers.

I played around a bit with your latest puzzle (233) to no avail. I tested with brute force for an odd number meeting the criteria up to about 40,000,000 with no solution. But yesterday, I did a search on google for info on "odd abundant numbers" and stumbled upon the definition of "weird numbers" (numbers with S(N)>N (ie. abundant) such that no subset sums to N). Then I saw references to a 1971 $10 reward offered by the late great Paul Erdos for the person who could find any odd weird number. Your puzzle 233 challenges us to find the 1st odd weird number, which is an even harder challenge than that of Erdos. Erdos would accept any odd weird number for his generous $10 offer. I am very curious to see what answers people come up with on this one. I can tell that in my ignorance, I expended a lot of computer time testing unlikely candidates with large numbers of factors and relatively large (S(N)-N), though to truly find the first such number, you would need to test every odd number or prove that some odd numbers can be excluded from testing.

PS. An excerpt from a paper by Benkoski called "Hubris, Weird Numbers, a Missing Asterisk, and Paul Erdos" that shows up on google mentions that the weird numbers up to 10^9 are "known" and that all "known" weird numbers are even. So it sounds like he is saying that any odd weird number is >10^9.

PPS. From looking at the even weird numbers (70=2.5.7 with S(70)=74, 836=2.2.11.19 with S(836)=844, 4030=2.5.13.31 with S(4030)=4034, it makes sense to me that if the goal is to find any odd weird number that it is likely to only have a small number of factors and have a very small [S(N)-N].

***

Are there abundant numbers odd N such that 'only have a small number of factors and have a very small [S(N)-N]'?... that is the question, now.

***

Wilfred Whiteside added some few days later:

Has someone found an odd weird yet? I sure haven't. The closest candidates I found so far are not all that close:

Systematic Search between 10^6 and 2*10^9 yields the following odd abundant numbers that have [S(N)-N]<100 :

number; S(N)-N; #factors; prime factors

20,355,825; 30; 71; 3.5.5.7.7.29.191
20,487,159; 18; 95; 3.3.7.11.17.37.47
78,524,145; 30; 47; 3.3.5.7.109.2287 (interesting that 2287=(3.7.109)-2
126,022,995; 90; 47; 3.3.5.7.107.3739 (3739=(5.7.3739)-6 = not quite the pattern)
159,030,135; 18; 95; 3.3.3.3.3.5.11.73.163

no other odd abundant with S(N)-N < 100 till past 2*10^9

Interesting that S(N)-N for these numbers only seem to be 18, 30, or 90. None of these numbers is "weird". I just think they are interesting.

He also sent a link to the Benkoski paper about weird numbers. You should download this paper. It is a little piece of good math art...

***

J. C Rosa appended some few days later several curio to the kind of numbers we are discussing about:

A- Odd numbers :

1) Palindromic abundant :

a) The first five :

5775=3.5.5.7.11 ; S=6129
50505=3.5.7.13.37 ;S=51639
53235=3.3.5.7.13.13 ;S=60957
55755=3.3.3.5.7.59 ; S=59445
171171=3.3.7.11.13.19 ; S=178269

b) two curios :

555555=3.5.7.11.13.37 ; S=670173
999999=3.3.3.7.11.13.37 ; S=1042881

2) Pandigital abundant numbers :

The smallest =1023476895 =3.3.5.7.19.171007 S=1110702945
The smallest not divisible by 5=1024356879 =3.37.13.17.29.43.59 S=1051316721

The largest =9876412035=3.3.5.7.37.593.1429 S=10265035005
The largest not divisible by 5=9875206341 =3.3.3.7.11.13.191.1913 S=9880948539

B- Even numbers :

1) Palindromic abundants numbers:

The first five :

66=2.3.11 ; S=78
88=2.2.2.11 ; S=92
222=2.3.37 ; S=234
252=2.2.3.3.7 ; S=476
272=2.2.2.2.17 ; S=286

2) Palindromic weird numbers:

The smallest: 2187812=2.2.11.19.2617 ; S(2187812)=2210428

In the Benkoski paper we can read :

" If n is weird and p is a prime with p>s(n)+n then pn is weird " And we have : 2187812=836*2617 836 is the second even weird number , s(836)=844 and s(836)+836 = 1680 ; 2617>1680. Thus 2187812 is a weird number . By using an even weird number ( 836 by example) we can easily obtain an even palindromic weird number N of the form : N=836*P with P prime , P>1680 Examples : 2187812=836*2617

2371732=836*2837
21499412=836*25717
and so on...

For obtain others even palindromic weird numbers we can also use the following weird numbers :7192 ; 7912 ; 9272 ; 10792

3) Pandigital abundant :

Note : An even pandigital number is a multiple of 6. 6 is a perfect number and we know that: " All number which is a multiple of a perfect number or of an abundant number is an abundant number " (It is easy to show it ) Thus all even pandigital number is an abundant number .

4) Pandigital weird number :

An even pandigital weird can not exist. Indeed , let N an even pandigital number. We have: N=18*A , ( A is an integer not necessarily prime). Among the proper divisors of N there is the subset : { 3*A, 6*A , 9*A } and 3*A+6*A+9*A=18*A=N. Therefore N is not a weird number.

***

Mike Oakes sent the following observations:

1. I have enumerated all odd abundant numbers <= 2*10^9.
There are 4096815 of them, giving a density estimate of 0.0020484.
This density is remarkably constant, being almost exactly the same for each of the 4 quarters of this range.

Of these, 59535 are "primitive" abundant, i.e. such that none of their aliquot divisors is abundant. This density, however, is not constant, but steadily decreasing, from 0.000042944 in the first quarter of the range to 0.00002977 in the 4th quarter. I conjecture it has asymptotic density zero.

2. What can we say about the so-called "abundance", A = sigma(N)-2*N ?

I have listed all A <= 1000 for N <= 2*10^9.

Since 2*N is even, A is odd iff sigma(N) is odd, i.e. iff for each factor p^s of N,  (p^s + p^(s-1) + .. + 1) is odd. So there must be an odd number of terms inside the ( ) bracket, i.e. s must be even for all p, i.e. N must be a perfect square.

There is only one A in the above range which is odd:-
N=11025=3^2*5^2*7^2, sigma(N)= 22971, A=921.
and it is indeed a perfect square.

If any factor p^s of N has p = 1 mod 6 with s even, or has p = 5 mod 6 with s odd, then sigma(N) is a multiple of 3. So, if N is a multiple of 3, which it is for all N <= 10^9, then A is also, unless there are no such factors p^s.

There are only 9 A in the above range which are not multiples of 3:-
N=1575=3^2*5^2*7, sigma(N)=   3224, A=74
N=4725=3^3*5^2*7, sigma(N)=   9920, A=470
N=6825=3*5^2*7*13, sigma(N)=  13888, A=238
N=78975=3^5*5^2*13, sigma(N)= 157976, A=26
N=236925=3^6*5^2*13, sigma(N)= 474362, A=512
N=9977175=3^4*5^2*13*379, sigma(N)=19955320, A=970
N=20220525=3^2*5^2*13*31*223, sigma(N)=40441856, A=806
N=116103225=3*5^2*7*37*43*139, sigma(N)=232207360, A=910
N=1408639575=3*5^2*7*19*283*499, sigma(N)=2817280000, A=850
and they all indeed have the described properties.

So, putting these 2 conclusions together, A is nearly always a multiple of 6. More detailed analysis shows that it is nearly always = 6 mod 12, in fact. And this ties in with Wilfred Whiteside's observations.

***

Phil Carmody wrote:

I decided to take a different approach from others in this puzzle, and not restrict myself to small values of n. Like Mike (Oakes), I've tried to find n such that abundance(n) is  small but positive. Many n which have negative abundance can be used as a building block to find larger n with positive abundance.

Foolishly I looked at a location where I'll never find a solution to the problem, but nevertheless I've found some exceptionally small abundances:

a n
630 18654437384294085
90 18907999191244799955
90 2393733692416703459777364533759955

I was looking somewhere where 90 always seems to divide the abundance (similar to the divisibility by 6 property that Mike mentioned), and where 90 is always creatable as a sum of divisors (33+57), which is why I'm destined to fail in this region. However, I decided where to look before I read Mike's post. Finding a region without this divisibility property is hard, or should I say finding any small abundances in such a region is hard.

I don't think the estate of Paul Erdos will be forking out $10 for a counter-example any time soon...

***

J. C. Rosa has demonstrated the following:

1) Among the odd numbers of the form a^n*b^m*p with 3<=a<b<p (a, b, p are prime numbers ) , the only ones that are abundant numbers are of the form : 3^n*5^m*7 or 3^n*5^m*11 or 3^n*5^m*13.

2) The abundant numbers of the form 3^n*5^m*7 or 3^n*5^m*11 are never weird numbers.

(The proof by mail on request)

***

 

 



Records   |  Conjectures  |  Problems  |  Puzzles