Talk:Giuga numbers
Is there a simpler way for generating the squarefree numbers
Giuga numbers are squarefree and therefor are simple product of different primes n = p1*p2..*pk.|p1<p2<..<pk
How big can the last prime factor pk get:
(n div pk -1) mod pk = z=[1,2,3...] | *pk
n div pk -1 = z*pk
(p1*p2*..*p(k-1))-1 = z*pk => pk must be a multible of (product of all other prime factors -1)
Examples:
2*3-1 = 5 ->pk= 5 -> n =2*3*5=30, no need to search on three factors starting with 2,3
2*3*7-1 = 41->pk= 41 -> n =2*3*7*41=1722
2*3*11-1 = 65 == z*pk AND pk>11 AND pk is divisor of 65 => pk =13 ->2*3*11*13 =858
2*3*11*17-1 = 1121 = z*pk == 19*59 -> pk =19 and 59 are possible to check 21318 and 66198
My intention is to extend the first k-1 prime factors and check for pk and then for guiga.
--Horsth (talk) 12:33, 2 July 2022 (UTC)
- found this on mersenneforum [Giuga numbers]
much faster. ~~----
- Presumably you meant <lang parigp>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)))))))</lang>
- I don't know why Pari-GP always seems to be written in this Code Golf fashion which makes it very difficult for simple folk such as me to understand. However, I can tell you that '\' is the Euclidean quotient operator which (in effect) rounds the result of the division to the lower integer towards zero. See here. Confusingly, it's also the line continuation token --PureFox (talk) 13:23, 14 July 2022 (UTC)