a propos divisors...

[N. J. A. Sloane]

On 7/25/07, Peter Pein <petsie at dordos.net> wrote:

> a) n such there is at least one x<n such that sigma(r,x)=sigma(r,n),
> because there exists such a series for r=1 (A069822)
>
> and
>
> b) a(n)=min({k>0: sigma(r,k)=sigma(r,n)})

[...]

> but for r = 3 the air becomes very thin. If I did not make a mistake,
> this seq starts(!):
>
> 194315, 295301, 590602, 1181204, 1476505, 1886920, 2067107, 2362408,
> 2526095, 2953010, 3248311, 3691985, 3838913, 4134214, 4469245, 4724816,
> 5020117, 5610719, 5635135, 5906020

[...]

> And if you want to make me really happy (I have had birthday on July
> 24th ;-) (http://www.stevesbeatles.com/songs/when_im_sixty_four.asp this
> age will be reached in 20 years, but the symptoms... )):

My congratulations!
Better late than never ;)

>  If you've got Mathematica and more RAM (4GB or so) than I do (1.5 GB),
> could you please run this code  with, say nmax=10 or 20 million? On my
> machine it swapped heavily with nmax=6 million and I had to kill
> MathKernel as I tried nmax=10^7. The lines above took ~181 seconds to
> evaluate (nmax=10^7 has been stopped by me after 15 minutes). I do not
> expect any runtimes of more than 7 minutes. Would this be possible, please?

These are the values below 10^7 that I got with my C++ program using
LiDIA library:

194315 184926
295301 291741
590602 583482
1181204 1166964
1476505 1458705
1886920 1880574
2067107 2042187
2362408 2333928
2526095 2404038
2953010 2917410
3248311 3209151
3691985 3513594
3838913 3792633
4134214 4084374
4469245 4253298
4724816 4667856
5020117 4959597
5610719 5543079
5635135 5362854
5906020 5834820
6023765 5732706
6496622 6418302
6791923 6710043
7382525 7293525
7677826 7585266
7966915 7581966
8268428 8168748
8355545 7951818
8563729 8460489
9132805 8691522
9449632 9335712

Each here line contains a pair:
n k
such that sigma(3,k)=sigma(3,n) and k=a(n) for r=3 (following your
notations above).

I will let my program to run for a couple more days to reach 10^8 bound.

> (AFAIK there exists no kind of "inverse
> function" to sigma(r,n) w.r.t. n which could be calculated without this
> brute-force method).

I disagree with this statement. There is a more or less clever way to
reconstruct the inverse of m=sigma(r,n) w.r.t. n, using integer
factorization of m and a kind of brute-force but of the magnitude of
the number of divisors of m.

Regards,
Max