Without going into a ton of detail as is the best of course
n=2,n=56,n=132 looks like the only ones that fit , you need d= (1+(4n+1)^(1/2)/2

but for every n=p1^m1*p2^m2*...pk^mk

d= (1+m1)*(1+m2)*...*(1+mk)

Basically d^2 doesnt grow as fast as n does so above n=840 the expression d^2-d is always smaller than n and its game over for the search.

For d^2-d to remain close to n, d must be real large which is accomplished by n being a factor of many primes as small as possible and some power of 2 with exponent larger or equal to 1 since n=d*(d-1) = even. Testing those kinds products leads fast to the conclusion only n=2 works.

I mean you look for 2^k things then 2^k*3, 2^k*3*5, 2^k*3*5*7,2^k*3^2, 2^k*3^2*5.

higher primes than 7 cannot help eg 11,13 because they only contribute to d a multiplicative factor of 2 with each prime added which is not enough to keep pace with the resulting rise of n. Higher exponents of them are even worse as they go from factor 2 to say 3 but the product (ie n) rises by that prime (11+) and cant catch up as 3^2<11 etc...

Basically the number n that we must be looking for is of the form 2^k*3^m*5^s*7^r*11^where m,s,r<3, w<=1 and those can be inspected by hand fast enough.

Basically the argument goes like you cant have big rimes in n because their existence doesnt contribute as much to d as their big size requires forcing d^2< n essentially very fast as the primes get big. So by inspection one finds what works a lot faster than it would seem because n cannot have big primes as factors.

I may make this more rigorous if i get the time lol.


The crude argument would go that if a prime pk is introduced to power mk it must not be true that for large enough pk pk^mk>>(1+mk)^2 which quickly proves true if say pk>7 ie 11,13 etc basically for each power of 11 you get 2^2 vs 11 or (2*2)^2=16 vs 11*13 etc quickly leaving d^2 smaller than n as n grows. 2^s*p type things or 2^s*p*q for p,k big primes are eliminated for these reasons as d^2=(2*2*(s+1))^2 <<2^s*p*q etc if p,q larger primes

It works for n = 56.

I'm wondering whether looking for integers k such that k = (#factors of k)(#factors of k-1) is any help.

I corrected my first answer to only 2,56,132,1260 within time limits, just try my line of arguments the big primes are eliminated fast and can only exist there with big powers of 2 and small 3,5,7 etc ie 1260,132,56. I almost always when i have solutions correct myself fast enough in these problems by the way so i still pass the exam Charlie lol, because i never gave back my exam to the testers as anything other than the last guy. All these solutions fit my suggested form of solutions by the way ie small primes to progressively smaller powers with maybe 2 powers larger etc.

Back from 49ers game. The sieve can be enhanced by also noticing that since n=d*(d-1) and d, d-1 have to be relatively prime then it must be true that;
div(n)=div(d*(d-1))=div(d)*div(d-1) so d=div(n) itself satisfies;

d=div(d)*div(d-1)

So if you check say 50 cases d from 2 to 50 you instantly eliminate cases that are prime numbers over 2 and cases that they dont satisfy d= div(d)*div(d-1) in general

For example if you had to check d=14=2*7 div(d)=4 and div (d-1=13)=2 so it fails before checking anything else.

This method quickly refines which ones you need to check thoroughly . So you do not need wasting too much time on the checking that is of course a less elegant proof but a proof nevertheless. All you need now is a convincing argument that d(n)^2<n for d(n)>50

Study the function (x+1)^2/p^x where p is any prime and establish what is the maximum of this function for each p.

This study will quickly tell you that if p is a prime factor of n then if p is 5 it cant have exponent over 2 if p is 7 cant have exponent of 1, if p is 11 cant have exponent over 1, if p is 13 cant have exponent over 1, and p cant be larger than 13. This quickly settles everything. Also 2 cant appear with exponent larger than 6, 3 larger than 4.
So you basically need to do this;

Check all numbers that have primes (factors) in small powers up to 13 ie 2,3,5,7,11,13 . Force exponent for 2 < 6 ,for 3<4 , for 5<3 for 7,11,13,17<2 also 2,3 appearing in high powers quickly removes all other primes so the checking needed is much less significant than one may think and doable within say 30 min after establishing this pattern and using also the prior test for d.

The highest one can get is for 2 to the 2 power , 3 to the 1st

Consider how n grows compared to d^2. If we have n' = p*n, then d' = (i+1)/i * d, where n' is of the form p^i * a with a not dividable by p.

p < (i+1)/i if (p = 2 and i = 1,2) or if (p = 3 and i = 1), so only the "first two" 2s and the "first" 3 make d^2 grow faster than n. So n = 12 maximises the ratio d^2/n at 3.

We use this information to see that if n < d^2 there can be:
-no factors of 13 in n (13/4 > 3)
-at most one factor of 7 or 11 in n ( 7^2/9 > 3)
-at most 2 factors 5 in n (5^3/16 > 3)

Additionally there are:
-at most 3 factors of 3 (4*3^4 > 9*5^2)
-at most 6 factors of 2 (3*2^7 > 4*8^2)

So n = 2^a 3^b 5^c 7^d 11^e with a < 7, b < 4, c < 3, d,e < 2
So d = (a+1)(b+1)(c+1)(d+1)(e+1)

Now n = d(d-1). So n is even (which means a>0) and not a perfect square (which means at least one of a,b,c,d,e is odd). So d is even and d-1 is odd.

So d = 2^a * x, and (d-1) = 3^b 5^c 7^d 11^e / x

In my last hint i gave the way to do it and a whole class of similar problems. I didnt present the entire proof though as it was obvious how it would go. But lets do it anyway. Now it may look like a brute force method but not really because you can trim it a lot by other properties.

We have n= d*(d-1) even. So 2 is a factor always to some power.

I gave that d= div(d)*div(d-1). That is very significant group of restrictions. Even for n as big as 10000 this forces to try less than 100 possible d values. But the property d= div(d)*div(d-1) for d>2 eliminates all primes from 3 to 100 and the as well as products of 2 primes only or 3 primes (for d not n) (we wills ee why later)

Then i suggested to look at the function (x+1)^2/p^x where p is a prime 2,3,5,7,11,13,17 etc

Here is a table of it that will prove useful because it helps examine what d^2/n does which is a bound condition for d^2-d=n. Ie if d^2<n for some n and higher there is no point in looking what d^2-d does, it can never be equal to n.

2----- 3----- 5----- 7----- 11------ 13------ 17-
1 2- 1.333333- 0.8- 0.571429- 0.363636- 0.307692- 0.235294
2 2.25- 1- 0.36- 0.183673- 0.07438- 0.053254- 0.031142
3 2- 0.592593- 0.128- 0.046647- 0.012021- 0.007283- 0.003257
4 1.5625-0.308642-0.04
5 1.125
6 0.765625
7 0.5



Now look what this table tells you right away. 13, 17 and higher cannot be factors of n because no combination with other primes to other powers can produce d^2/n>1, So only factors with 11,7,5,3,2 survive.


If 11 was a factor then this forces right away 5 or 7 to be impossible to be factors as well because then no power of 2 or 3 or both can recover the d^2/n>1. So 11 if factor can only be combined with 2 and 3 in powers. In fact it cant be 3^2 because then no power of 2 can recover the d^2/n over 1. So if 3 is a factor also then its 3^1 and then 2 has to be to the second power necessarily to barely make it all over 1.

So we have the only possible result involving all 2,3,11 and it is 2^2*3*11=132 which by the way is a solution because d(132)=3*2*2=12 and 12^2-12=132 as needed.

The point here though is that with 11 involved the largest number that could be true is 132. No higher multiples of 11 can exist.

That does it for 11 now and we can consider cases 11 is not involved.

Starting with 7 now we see that 7 cannot be in second power if there. Furthermore if its in the first power if 5 is also involved (only first power possible then) then this forces the maximum possible allowed number to be 2^2*3^2*5*7 =1260 (the others are smaller combinations). By the way 1260 is a solution also since d(1260)=3*3*2*2=36 and 36^2-36=1260.

The important thing established here is that the biggest number possible is 1260. No larger number can exist to make the products over 1 if 7 is involved. And if 7 is not involved then the 5 can be at most in second power needed then 2^2 and 3^1 (the result 300 is still smaller than 1260). Any other combination with 5^1 is still at most 3^3*2^2*5=540. Without 5 involved the maximum possible number is 2^3*3^3=216<1260.

The above essentially suggest that n is at most 1260 and d<1260^(1/2)<=35.

In fact the above discussion eliminates all of the n from 1260 to 540 as well so we need to check only from 540 and lower. which is for n<=23

Now that settles it fast.

since d= div(d)*div(d-1)

look how fast we crash everything.

23 fails,22=2*11 fails, 21=3*7 fails (ie div 21 is not 3 or 7), 20 fails because 20^2-20=380=19*5*2*2 that has d(380)=12 not 20, 19=1*19 fails, 18 also fails because 18^2-18=306=2*3^2*17 that has d(306)=12 and 12^2-12=132 not 306, 17 =1*17 fails, 16 would want n to be 240 and d*240)=d(2^4*3*5)=20 and so 20^2-20=380 not 240, 15 =3*5 fails (div 15 isnt 3 or 5), 14=2*7 also fails same reason, 13=1*13 same reason fails,12=3*2*2 doesnt fail the div12*div11=d=12 test and in fact 12^2-12=132 and div (132)=div(2^2*3*11)=3*2*2=12 so its a solution. d=11 fails, d=10=2*5 fails, d=9 =3*3 fails ,d=8 has 8^2-8=56 and d(56=7*2^3)=2*4=8 so n=56 is a solution, d=7 fails, d=6=2*3 fails, d=5 fails, d=4 fails, d=3 fails, d=2 passes as d(2)=2 and 2^2-2=2, 1 fails too.

That does it . We found n=2,56,132 and 1260 and nothing else can satisfy it as shown.

The fact is the above eliminations are not even necessary because the power analysis before took care of what are the possible combinations of powers 2,3,5,7,11 that make sense but because those were bounds (didnt take all possible branches i mean) i did the full thing to be sure knowing i had to look only sub d=24.

I of course still dont see this as very elegant but its not brute force in the real not practical sense either.

"So d = 2^a * x, and (d-1) = 3^b 5^c 7^d 11^e / x"

So I just noticed that the 'd-1' part means that the 3s, 5s etc can't be split up between d and d-1. That shouldn't have taken me that long haha. Think I'll get a nice looking solution soon.