

A195239


Related to FNV primes: Least 0 < m < 256 with 4 or 5 1bits such that 2^n + 256 + m > 16777600 (mod 1099494850560), or 0 if no such m exists.


1



147, 55, 47, 47, 39, 23, 89, 47, 45, 43, 39, 77, 0, 31, 23, 53, 179, 43, 71, 103, 75, 29, 117, 197, 59, 23, 89, 77, 39, 31, 89, 55, 147, 71, 143, 169, 59, 109, 47, 103, 51, 205, 209, 139, 89, 29, 47, 29, 167, 205, 107, 47, 0, 61, 53, 103, 87, 53, 83, 85, 71, 143, 51, 43
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

24,1


COMMENTS

The FNVprimes for n=8*trunc((2^s+5)/12) and s=5..11 are used in FNV hashes: 24, 40, 88, 168, 344, 680, and 1368.
a(n) = 0 for almost all n, thus the fraction of bit sizes suitable for the FNV hash is asymptotically smaller than any fixed fraction. In practice this is not an issue since required sizes are small and for large values some nearby size can be chosen instead.  Charles R Greathouse IV, Apr 10 2012


LINKS



EXAMPLE

a(24)=147 is binary 10010011, 2^24 + 256 + 147 = 16777619 is prime, and 16777619 > 16777600 (mod 1099494850560). With 24 = 8*trunc((2^5 + 5)/12) this prime is used for 2^5 = 32bit FNVhashing. For 2^6 = 64bit FNVhashing a(40)=179 with 40 = 8*trunc((64 + 5)/12) determines the FNVprime 1099511628211.


MATHEMATICA

a[n_] := Module[{t}, For[m = 15, m <= 241, m++, t = DigitCount[m, 2, 1]; If[t > 3 && t < 6 && PrimeQ[t = m + 2^n + 256] && Mod[t, 1099494850560] > 16777600, Return[m]]]; 0]; Table[a[n], {n, 24, 100}] (* JeanFrançois Alcover, Oct 10 2017, translated from PARI *)


PROG

(PARI) a(n)=my(t); for(m=15, 241, t=vecsum(binary(m)); if(t>3&&t<6&& isprime(t=2^n+256+m)&&t%1099494850560>16777600, return(m))); 0 \\ Charles R Greathouse IV, Apr 10 2012


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



