Talk:Giuga numbers

From Rosetta Code
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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)
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>

But I'm having problems reading that code. Specifically: for(i=1,(length(f)+1)\2,h=f[i] -- I haven't been able to find any documentation on what \2 means in this context. Do you know where I should be looking? --Rdm (talk) 13:00, 14 July 2022 (UTC)
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)
And the '\' is the comment character (when doubled, but that still makes string searches laborious). But, yes... I think I understand \ for the real domain (parigp also supports other domains and I haven't seen examples of how those play out, but... hopefully that's not an issue here -- though, from my perspective lack of illustrative examples is more difficult to deal with than the "code golf" presentation, perhaps less difficult than typos (such as we see in the examples for '%' in the reference).
Anyways, thanks -- I think I have enough here to go on, ... though I'm not completely sure, yet. --Rdm (talk) 14:25, 14 July 2022 (UTC)