Giuga numbers

[grandpascorpion]

Hello,

I bumped into this at: http://www.primepuzzles.net/puzzles/puzz_327.htm

Overview:
http://mathworld.wolfram.com/GiugaNumber.html

In-depth article:
http://www.math.uwo.ca/~dborwein/cv/giuga.pdf

Just curious, if anyone has looked into finding more values or relations.

[grandpascorpion]

1910667181420507984555759916338506
= 2 * 3 * 7 * 43 * 1831 * 138683 * 2861051 * 1456230512169437

There's no other solutions with <= 8 prime factors. I did an exhaustive search.

[R. Gerbicz]

Originally Posted by grandpascorpion

1910667181420507984555759916338506
= 2 * 3 * 7 * 43 * 1831 * 138683 * 2861051 * 1456230512169437

There's no other solutions with <= 8 prime factors. I did an exhaustive search.

I've also rediscovered that solution when the problem appeared on primepuzzles.net, but that is a known solution. One more solution is known with 10 primes factors!!!!!
n=4200017949707747062038711509670656632404195753751630609228764416142557211582098432545190323474818=
2*3*11*23*31*47059*2217342227*1729101023519*8491659218261819498490029296021*58254480569119734123541298976556403

See this article: http://www.ams.org/mcom/2000-69-229/...99-01088-1.pdf

[grandpascorpion]

Weird, it was already known but it wasn't added to the integer sequence website.

Just curious, if you had found this yourself at the time, why didn't you raise it with them?

That 10 factor number is a behemoth!

[R. Gerbicz]

Originally Posted by grandpascorpion

Just curious, if you had found this yourself at the time, why didn't you raise it with them?

I've sent an email to rivera, that I've found a new term, but no answer and he hasn't responded to my email. I think that was my first and last email to him.

It took me about 1300 sec to find all proper Giuga sequence of length 8, using only trial divison and Pollard-rho method for factorization. There was 826025 sequences for length 8. To give a complete list:
n=4
1722, Sequence number=1
858, Sequence number=1
Number of initial sequences=2
Time=0.00 secs.
n=5
66198, Sequence number=2
Number of initial sequences=5
Time=0.00 secs.
n=6
24423128562, Sequence number=1
2214408306, Sequence number=20
Number of initial sequences=36
Time=0.00 secs.
n=7
432749205173838, Sequence number=622
550843391309130318, Sequence number=755
14737133470010574, Sequence number=755
Number of initial sequences=1260
Time=0.30 secs.
n=8
1910667181420507984555759916338506, Sequence number=123973
554079914617070801288578559178, Sequence number=815089
244197000982499715087866346, Sequence number=815096
Number of initial sequences=826025
Time=1306.75 secs.

This is obtained by GMP.
A PARI-GP version of the program:

a(n)=print("n=",n);s=p=vector(n-2);t=p[1]=p[2]=2;s[1]=1/2;\
while(t>1,p[t]=nextprime(p[t]+1);s[t]=s[t-1]+1/p[t];\
if(s[t]==1||s[t]+(n-t)/p[t]<=1,t--,\
if(t<n-2,t++;p[t]=max(p[t-1],s[t-1]/(1-s[t-1])),\
c=numerator(s[n-2]);d=denominator(s[n-2]);k=d^2+c-d;f=divisors(k);\
for(i=1,(length(f)+1)\2,h=f[i];if((h+d)%(d-c)==0&&(k/h+d)%(d-c)==0,\
r1=(h+d)/(d-c);r2=(k/h+d)/(d-c);\
if(r1>p[n-2]&&r2>p[n-2]&&r1!=r2&&isprime(r1)&&isprime(r2),\
w=d*r1*r2;print(w);write("giuga.txt",w)))))))

To use it just print for example a(7) and you'll have got all Giuga numbers for length 7 in less than 1 sec. I think it took about 4 hours for length 8.

[grandpascorpion]

Yep, I have a PARI script that I wrote that's quite similar. Thanks. BTW, there's a keyword in PARI called fordiv to iterate through the divisors of a number.

I have started searching for 9 factor numbers but that's running about 30 times as slow and there's upwards of 60 billion cases to check.