View Single Post
2019-05-10, 06:31   #11
hansl

Apr 2019

5·41 Posts

Quote:
 Originally Posted by axn There are 8 modular classes that don't have trivial factors (mod 30). These are {1,7,11,13,17,19,23,29}. So you use 8 bitmaps each of length 2^32/30 bits. The first bitmap will store all numbers of the form 1+30n -- bit 0 will be 1, bit 1 will be 31, bit 2 will be 61, etc.. Second bitmap will store 7+30n, and so on. Total size for all these bitmaps would be (2^32/30)*8 bits or 2^32/30 byte which is about 136.5 MB. To see if a number k > 5 and < 2^32 is prime, decompose k into q = floor(k/30), r=k%30 if r is not one of {1,7,11,13,17,19,23,29}, it is not prime. Else lookup qth bit from the appropriate bitmap.
Ah, thanks, I think I get it now.

I worked out some functions to help calculate storing up to various bit limits with different wheel sizes. I figured the modular classes for large wheels could be stored as gaps between classes, so many of the functions rely on looking up prime gaps from tables:
Code:
bits(n) = ceil(log(n)/log(2));

\\ Nth Primorial (product of the first n primes)
nthprimorial(n)=prod(i=1,n,prime(i));

\\ Primorial (product of all primes <= n)
primorial(n)=nthprimorial(primepi(n));

\\ number of primes < nthprimorial(n) (see https://oeis.org/A000849 )
nthprimorialpi(n)={my(a=[0,1,3,10,46,343,3248,42331,646029,12283531,300369796,8028643010,259488750744,9414916809095,362597750396740,15397728527812858,742238179058722891,40068968501510691894]);
if(n>#a-1,print("error, unknown for n>",#a-1),a[n+1]);}

\\ number of primes < primorial(n)
primorialpi(n)=nthprimorialpi(primepi(n));

\\ nth maximal gap between primes (see https://oeis.org/A005250 )
maxgap(n)={my(gaps=[1,2,4,6,8,14,18,20,22,34,36,44,52,72,86,96,112,114,118,132,148,154,180,210,220,222,234,248,250,282,288,292,320,336,354,382,384,394,456,464,468,474,486,490,500,514,516,532,534,540,582,588,602,652,674,716,766,778,804,806,906,916,924,1132,1184,1198,1220,1224,1248,1272,1328,1356,1370,1442,1476,1488,1510,1526,1530,1550]);
gaps[n]}

\\ max gap between primes for all p <= prime(n) (see https://oeis.org/A005669 )
maxgap_nthprime(n)={my(gap_prime_ns=[1,2,4,9,24,30,99,154,189,217,1183,1831,2225,3385,14357,30802,31545,40933,103520,104071,149689,325852,1094421,1319945,2850174,6957876,10539432,10655462,20684332,23163298,64955634,72507380,112228683,182837804,203615628,486570087,910774004,981765347,1094330259,1820471368,5217031687,7322882472,9583057667,11723859927,11945986786,11992433550,16202238656,17883926781,23541455083,28106444830,50070452577,52302956123,72178455400,94906079600,251265078335,473258870471,662221289043,1411461642343,2921439731020,5394763455325,6822667965940,35315870460455,49573167413483,49749629143526,1175661926421598,1475067052906945,2133658100875638,5253374014230870,5605544222945291,7784313111002702,8952449214971382,10160960128667332,10570355884548334,20004097201301079,34952141021660495,135962332505694894,160332893561542066,360701908268316580,408333670434942092,423731791997205041]);
for(i=1,#gap_prime_ns,if(gap_prime_ns[i]>n,return(gap_prime_ns[i-1]),if(gap_prime_ns[i]==n,return(maxgap(i)))));print("n=",n," max gap unknown for n > ",gap_prime_ns[#gap_prime_ns]," guess 2047?"); 2047}

\\ max gap between primes prime gap for primes <= n (see https://oeis.org/A000101 )
maxgap_n(n)={my(gap_primes=[3,5,11,29,97,127,541,907,1151,1361,9587,15727,19661,31469,156007,360749,370373,492227,1349651,1357333,2010881,4652507,17051887,20831533,47326913,122164969,189695893,191913031,387096383,436273291,1294268779,1453168433,2300942869,3842611109,4302407713,10726905041,20678048681,22367085353,25056082543,42652618807,127976335139,182226896713,241160624629,297501076289,303371455741,304599509051,416608696337,461690510543,614487454057,738832928467,1346294311331,1408695494197,1968188557063,2614941711251,7177162612387,13829048560417,19581334193189,42842283926129,90874329412297,171231342421327,218209405437449,1189459969826399,1686994940956727,1693182318747503,43841547845542243,55350776431904441,80873624627236069,203986478517457213,218034721194215521,305405826521089141,352521223451365651,401429925999155063,418032645936713497,804212830686679111,1425172824437700887,5733241593241198219,6787988999657779307,15570628755536096243,17678654157568189057,18361375334787046697]);
for(i=1,#gap_primes,if(gap_primes[i]>n,return(gap_primes[i-1]),if(gap_primes[i]==n,return(maxgap(i)))));print("n=",n," max gap unknown for n > ",gap_primes[#gap_primes]," guess 2047?"); 2047}

\\ size of wheel factorization bitmap for storing all primes < 2^b, using a nthprimorial(n) base wheel
wheelbitmapMiB(b, n)=2.^(b-23)/nthprimorial(n)*eulerphi(nthprimorial(n));

\\ size of wheel itself for wheel factorization, using a nthprimorial(n) base wheel. Storing the gap between each modular class
wheelMiB(n)=(eulerphi(nthprimorial(n))-1)*bits(maxgap_n(nthprimorial(n))/2)/2.^23

\\ total size of wheel and bitmap for storing all primes < 2^b, using a nthprimorial(n) base wheel
wheeltotalMiB(b, n)=wheelMiB(n)+wheelbitmapMiB(b,n);

\\primorial_numeral(n)= \\ Convert to primorial number system, vector of digits
And here's the results I got
Code:
? wheeltotalMiB(32,3)
%305 = 136.5333366711934407552083333
? wheeltotalMiB(32,4)
%306 = 117.0286050455910818917410714
? wheeltotalMiB(32,5)
%307 = 106.3901814021073378525771104
? wheeltotalMiB(32,6)
%308 = 98.21540557397352708326829421
? wheeltotalMiB(32,7)
%309 = 92.62673454240674648048412984
? wheeltotalMiB(32,8)
%310 = 91.91488279250780099343562301
? wheeltotalMiB(32,9)
%311 = 201.2229731159129979738501068
? wheeltotalMiB(40,8)
%312 = 22420.81124958361143420233199
? wheeltotalMiB(40,9)
%313 = 21559.29775874218603843453359
? wheeltotalMiB(40,10)
%314 = 24600.58342260438659563560571
? wheeltotalMiB(40,11)
%315 = 155250.8481199464342168732928
? wheeltotalMiB(48,10)
%316 = 5303727.482159470771217090061
? wheeltotalMiB(48,11)
%317 = 5264083.330768526806431184056
? wheeltotalMiB(48,12)
%318 = 10515841.27706460812349303656
? wheeltotalMiB(56,11)
%319 = 1313125198.888805102093294739
? wheeltotalMiB(56,12)
%320 = 1283029359.117316411105306225
? wheeltotalMiB(56,13)
%321 = 1493681169.718112853646773902
? wheeltotalMiB(64,12)
%322 = 327046489926.2217779744494826
? wheeltotalMiB(64,13)
%323 = 319311691479.0883192569093850
? wheeltotalMiB(64,14)
%324 = 322695438533.3537066932409118
So, based on this code, best case for 2^32 could be stored in 91.9MiB, using a 8## wheel.

2^40 in ~21.6 GB using mod 9## wheel
2^48 in ~5.26 TB using mod 11## wheel
2^56 in ~1.28 PB using mod 12## wheel
2^64 in ~319 PB using mod 13## wheel

Quote:
 Originally Posted by ATH If you go to a mod-210 wheel there are 48 modular classes so 6 bytes for every 210 numbers so 2^32 in 117 MB (122.7M bytes).
Oops, and I just realized that I'm not calculating the modular classes correctly, I thought it would be primepi(nthprimorial(n))-n+1, but I guess that misses all the composites which should still be included? So actual estimates would be a bit(a lot?) higher than the above results.

Is there a formula to get the modular classes given the nth primorial?

edit: Fixed code and results, Thanks LaurV!

Last fiddled with by hansl on 2019-05-10 at 06:54 Reason: Updated code and data with proper modular class count