/*****************************************************************************/ /* http://www.research.att.com/~njas/sequences/primestats.c.txt */ /* */ /* Coded by Antti Karttunen (Antti.Karttunen(-AT-)iki.fi), May-June 2004, */ /* except the prime sieve part (functions compute_primes and assorted */ /* clear_one_mask_bit and test_one_mask_bit in the end of this source file) */ /* which are copyright 1999-2004 by John Moyer, (jrm(-AT-)rsok.com), */ /* http://www.rsok.com/~jrm/ */ /* */ /* This program computes the sequences A095005 - A95024 & A095051 - A095095 */ /* that are found in */ /* Neil Sloane's On-Line Encyclopedia of Integer Sequences (OEIS) */ /* available at */ /* http://www.research.att.com/~njas/sequences/ */ /* */ /* TO DO: In case we would like to compute up to higher n than 33 or such */ /* we should implement some probabilistic prime checking algorithm, */ /* which might be slower to execute, but needs almost no RAM at all. */ /* */ /* If you add your own additions, please send the improved source back to */ /* me Antti.Karttunen(-AT-)iki.fi so I can then send the updated version */ /* to Neil Sloane at njas(-AT-)research.att.com to be placed in this */ /* same address. */ /* */ /* Last edited June 4 2004 by Antti Karttunen: */ /* Compute 44 new sequences, in ranges */ /* A095280-A095298, A095312-A095336 & A095353-A095354. */ /* */ /*****************************************************************************/ /* Compile as gcc -O3 -o primestats primestats.c -lm in Linux/Unix. */ #include #include #include #include #include /**********************************************************************/ /* */ /* */ /* This part by Antti Karttunen. Collect statistics for certain */ /* OEIS-sequences. */ /* */ /* */ /**********************************************************************/ typedef unsigned long long int ULLI; /* 64 bits at our disposal. */ typedef unsigned long int ULI; /* Plain 32 with no frills. */ int glob_dyckness_checked_only_up_to_n = 16; #define power_of_2(i) (((ULLI)1) << (i)) /* See the section "Number Conversion" at the end of the excerpt: http://www.iki.fi/kartturi/matikka/kl10exmp.txt */ int fprint_ulli(FILE *fp,ULLI x) { int s = 0; if(x >= 10) { s = fprint_ulli(fp,(x/((ULLI)10))); } fputc(('0' + (x%((ULLI)10))),fp); return(s+1); } /* Max exp-value 63 is surely enough. Nobody will compute up to that many terms in the foreseeable future. */ #define vec65zeros { 0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0 }; #define vec128zeros { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; /* Like above, but we have prefilled the position 1 of the vector with the first prime 2, so that the prime_found continues filling it from the position 2. (Because out starting point is 3, as to avoid handling of the unique even prime 2. */ #define vec128_with_initial_2 \ { 1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }; /* (fibo 93) = 12200160415121876738 is the last Fibonacci less than 18446744073709551616 as (fibo 94) = 19740274219868223167. */ #define COMPUTE_FIBOS_UP_TO 93 ULLI vecA000045[128] = vec128zeros; /* Fibonacci numbers. Precompute them! */ #define A000045(n) (vecA000045[n]) ULLI vecA003714[128] = vec128zeros; /* Fibbinary numbers. Compute a sample. */ void precompute_fibos_to_vector(ULLI *vec,int upto_n) { int i; vec[0] = 0; vec[1] = 1; for(i=2; i <= upto_n; i++) { vec[i] = vec[i-1]+vec[i-2]; } } int index_of_largest_fibo_present(ULLI n) { int ind = COMPUTE_FIBOS_UP_TO; /* Slightly dumb, yes. */ /* Note that when n=0, the loop ends when ind=0, as A000045(0)=0 */ while(n < A000045(ind)) { ind--; } return(ind); } ULLI A003714(ULLI orig_n) { ULLI n = orig_n; ULLI z = 0; while(n != 0) { int i = index_of_largest_fibo_present(n); n -= A000045(i); if(i > (63+2)) { /* We are interested only about the three least significant fibits, thus we can safely ignore the higher fibits, especially if they would corrupt the result because of index wrap-over: */ fprintf(stderr,"A003714("); fprint_ulli(stderr,n); fprintf(stderr,") resulted a fib-index %u > 65, ignored.\n",i); } else { z |= power_of_2(i-2); } } return(z); } /* precompute_fibos_to_vector should have been called first! */ void precompute_fibbinaries_to_vector(ULLI *vec,int upto_n) { int i; for(i=0; i <= upto_n; i++) { vec[i] = A003714((ULLI)i); } } ULLI vecA036378[65] = vec65zeros; /* Here are the 20 A-numbers you requested: 95005 --- 95024. */ /* Here are the 60 A-numbers you requested: 95052 --- 95111. */ /* Here are the 30 A-numbers you requested: 95269 --- 95298. */ /* Here are the 25 A-numbers you requested: 95312 --- 95336. */ /* Here are the 12 A-numbers you requested: 95353 --- 95364. */ ULLI vecA095005[65] = vec65zeros; /* # of Odious primes (A027697). */ ULLI vecA095006[65] = vec65zeros; /* # of Evil primes (A027699). */ ULLI vecA027697[128] = vec128_with_initial_2; /* Odious primes. */ ULLI vecA027699[128] = vec128zeros; /* Evil primes. */ ULLI vecA095007[65] = vec65zeros; /* Primes of the form 4k+1. */ ULLI vecA095008[65] = vec65zeros; /* Primes of the form 4k+3. */ ULLI vecA095009[65] = vec65zeros; /* Primes of the form 8k+1. */ ULLI vecA095010[65] = vec65zeros; /* Primes of the form 8k+3. */ ULLI vecA095011[65] = vec65zeros; /* Primes of the form 8k+5. */ ULLI vecA095012[65] = vec65zeros; /* Primes of the form 8k+7. */ ULLI vecA095013[65] = vec65zeros; /* Primes of the form 8k+-1. */ ULLI vecA095014[65] = vec65zeros; /* Primes of the form 8k+-3. */ ULLI vecA095015[65] = vec65zeros; /* Primes of the form 6k+1. */ ULLI vecA095016[65] = vec65zeros; /* Primes of the form 6k+5. */ ULLI vecA095017[65] = vec65zeros; /* Lesser twin primes (less than A095016). */ ULLI vecA095018[65] = vec65zeros; /* Binarily balanced primes (A066196). */ ULLI vecA095052[65] = vec65zeros; /* # Primes with one more 0- than 1-bits. */ ULLI vecA095053[65] = vec65zeros; /* # Primes with one more 1- than 0-bits. */ ULLI vecA095056[65] = vec65zeros; /* Primes with three 1-bits (A081091). */ ULLI vecA095057[65] = vec65zeros; /* Primes with four 1-bits (A095077). */ ULLI vecA095058[65] = vec65zeros; /* # Primes with just one 0-bit. (A095078) */ ULLI vecA095059[65] = vec65zeros; /* # Primes with just 2 0-bits. (A095079) */ ULLI vecA095060[65] = vec65zeros; /* # fibeven primes (A095080). */ ULLI vecA095080[128] = vec128_with_initial_2; /* fibeven primes. */ ULLI vecA095061[65] = vec65zeros; /* # fibodd primes (A095081). */ ULLI vecA095081[128] = vec128zeros; /* fibodd primes. */ ULLI vecA095062[65] = vec65zeros; /* # fib00 primes (A095082). */ ULLI vecA095082[128] = vec128zeros; /* fib00 primes. */ ULLI vecA095063[65] = vec65zeros; /* # fibodious primes (A095083). */ ULLI vecA095083[128] = vec128_with_initial_2; /* fibodious primes. */ ULLI vecA095064[65] = vec65zeros; /* # fibevil primes (A095084). */ ULLI vecA095084[128] = vec128zeros; /* fibevil primes. */ ULLI vecA095065[65] = vec65zeros; /* # fib000 primes (A095085). */ ULLI vecA095085[128] = vec128zeros; /* fib000 primes. */ ULLI vecA095066[65] = vec65zeros; /* # fib001 primes (A095086). */ ULLI vecA095086[128] = vec128zeros; /* fib001 primes. */ ULLI vecA095067[65] = vec65zeros; /* # fib010 primes (A095087). */ ULLI vecA095087[128] = vec128zeros; /* fib010 primes. */ ULLI vecA095068[65] = vec65zeros; /* # fib100 primes (A095088). */ ULLI vecA095088[128] = vec128zeros; /* fib100 primes. */ ULLI vecA095069[65] = vec65zeros; /* # fib101 primes (A095089). */ ULLI vecA095089[128] = vec128zeros; /* fib101 primes. */ ULLI vecA095021[65] = vec65zeros; /* Primes of the form 5k+1. */ ULLI vecA095022[65] = vec65zeros; /* Primes of the form 5k+2. */ ULLI vecA095023[65] = vec65zeros; /* Primes of the form 5k+3. */ ULLI vecA095024[65] = vec65zeros; /* Primes of the form 5k+4. */ ULLI vecA095072[128] = vec128zeros; /* Primes with one more 0- than 1-bits. */ ULLI vecA095073[128] = vec128zeros; /* Primes with one more 1- than 0-bits. */ ULLI vecA095077[128] = vec128zeros; /* Primes with four 1-bits. */ ULLI vecA095078[128] = vec128_with_initial_2; /* Primes with a single 0-bit. */ ULLI vecA095079[128] = vec128zeros; /* Primes with two 0-bits. */ ULLI vecA095090[65] = vec65zeros; /* Number of 4k+3 nums with Motzkin path */ ULLI vecA095100[128] = vec128zeros; /* 4k+3 n w/ Jacobi-vec = Motzkin path */ ULLI vecA095091[65] = vec65zeros; /* Number of 4k+3 n w/out Motzkin path */ ULLI vecA095101[128] = vec128zeros; /* 4k+3 n w/ Jacobi-vec != Motzkin path */ ULLI vecA095109[65] = vec65zeros; /* Sum of A095269 */ ULLI vecA095110[65] = vec65zeros; /* Sum of A095270 */ ULLI vecA095269[128] = vec128zeros; /* Diving index for 4n+1. */ ULLI vecA095270[128] = vec128zeros; /* Max Motzkin-path prefix for 4n+1. */ ULLI vecA095271[128] = vec128zeros; /* Diving index for nth A095101. */ ULLI vecA095272[128] = vec128zeros; /* (A095102(n)-3)/4. */ ULLI vecA095273[128] = vec128zeros; /* (A095103(n)-3)/4. */ ULLI vecA095274[128] = vec128zeros; /* (A095100(n)-3)/4. */ ULLI vecA095275[128] = vec128zeros; /* (A095101(n)-3)/4. */ ULLI vecA095092[65] = vec65zeros; /* Number of A095102 primes. */ ULLI vecA095102[128] = vec128zeros; /* 4k+3 pr. w/ Legendre-vec = Dyck path */ ULLI vecA095093[65] = vec65zeros; /* Number of A095103 primes. */ ULLI vecA095103[128] = vec128zeros; /* 4k+3 pr. w/ Legendre-vec != Dyck path */ ULLI vecA095104[128] = vec128zeros; /* Diving index for nth (A002145). */ ULLI vecA095105[128] = vec128zeros; /* Max Dyck-path prefix for nth A002145. */ ULLI vecA095106[65] = vec65zeros; /* Sum of A095104. */ ULLI vecA095107[65] = vec65zeros; /* Sum of A095105. */ ULLI vecA095108[128] = vec128zeros; /* Diving index for the nth A095103. */ ULLI vecA095094[65] = vec65zeros; /* Number of A080114 primes. */ ULLI vecA080114[128] = vec128zeros; /* Primes with valid Dyck path. */ ULLI vecA095095[65] = vec65zeros; /* Number of A080115 primes. */ ULLI vecA080115[128] = vec128_with_initial_2; /* Primes not in A080114. */ ULLI vecA095280[128] = vec128zeros; /* Primes in A000201. */ ULLI vecA095290[65] = vec65zeros; ULLI vecA095281[128] = vec128_with_initial_2; /* Primes in A001950. */ ULLI vecA095291[65] = vec65zeros; ULLI vecA095282[128] = vec128_with_initial_2; ULLI vecA095292[65] = vec65zeros; ULLI vecA095283[128] = vec128zeros; /* Primes in A079523. */ ULLI vecA095293[65] = vec65zeros; ULLI vecA095320[128] = vec128_with_initial_2; /* #1-bits > #0-bits - 3 */ ULLI vecA095330[65] = vec65zeros; ULLI vecA095321[128] = vec128zeros; /* #1-bits <= #0-bits - 3 */ ULLI vecA095331[65] = vec65zeros; ULLI vecA095316[128] = vec128_with_initial_2; /* #1-bits > #0-bits - 2 */ ULLI vecA095326[65] = vec65zeros; ULLI vecA095317[128] = vec128zeros; /* with #1-bits <= #0-bits - 2 */ ULLI vecA095327[65] = vec65zeros; ULLI vecA095074[128] = vec128_with_initial_2; /* #1-bits > #0-bits - 1 */ ULLI vecA095054[65] = vec65zeros; /* # Primes that are not zero-dominant. */ ULLI vecA095071[128] = vec128zeros; /* #1-bits <= #0-bits - 1. */ ULLI vecA095019[65] = vec65zeros; /* # Zero-bit dominant primes (A095071). */ ULLI vecA095070[128] = vec128zeros; /* #1-bits > #0-bits. 1-bit dominants. */ ULLI vecA095020[65] = vec65zeros; /* # One-bit dominant primes (A095070). */ ULLI vecA095075[128] = vec128_with_initial_2; /* Not 1-bit-dominant primes. */ ULLI vecA095055[65] = vec65zeros; /* # Primes that are not one-bit-dominant. */ ULLI vecA095286[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 1 */ ULLI vecA095296[65] = vec65zeros; ULLI vecA095287[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 1 */ ULLI vecA095297[65] = vec65zeros; ULLI vecA095314[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 2 */ ULLI vecA095334[65] = vec65zeros; ULLI vecA095315[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 2 */ ULLI vecA095335[65] = vec65zeros; ULLI vecA095318[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 3 */ ULLI vecA095328[65] = vec65zeros; ULLI vecA095319[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 3 */ ULLI vecA095329[65] = vec65zeros; ULLI vecA095322[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 4 */ ULLI vecA095324[65] = vec65zeros; ULLI vecA095323[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 4 */ ULLI vecA095325[65] = vec65zeros; ULLI vecA095284[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 5 */ ULLI vecA095294[65] = vec65zeros; ULLI vecA095285[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 5 */ ULLI vecA095295[65] = vec65zeros; ULLI vecA095312[128] = vec128zeros; /* Primes with #1-bits > #0-bits + 6 */ ULLI vecA095332[65] = vec65zeros; ULLI vecA095313[128] = vec128_with_initial_2; /* with #1-bits <= #0-bits + 6 */ ULLI vecA095333[65] = vec65zeros; ULLI vecA095298[65] = vec65zeros; ULLI vecA095336[65] = vec65zeros; /* Sum 1-fibits in odd primes in ]2^n,2^n] */ ULLI vecA095353[128] = vec128zeros; /* Sum of 1-fibits in odd primes in range [F(n+1),F(n+2)[ */ ULLI vecA095354[128] = vec128zeros; /* Occurrences of primes in that range. */ void fprint_ULLI_vector(FILE *fp,ULLI *vec,int start,int end) { int i; for(i=start; i <= end; i++) { if(i>start) { fprintf(fp,","); } fprint_ulli(fp,*(vec+i)); } } /* Returns the number of terms printed if finished because no more fits, zero otherwise, when everything has been printed. */ int fprint_ULLI_vector_in_pieces(FILE *fp,ULLI *vec, int start,int end,int max_linelen,int islast) { int i=start; /* Number of terms printed this time. */ int pl=0; /* Print length. */ for(;;) { pl += fprint_ulli(fp,vec[i++]); if(i > end) { return(0); } /* Finished the vector */ if(islast && ((pl+1) >= max_linelen)) { return(i-start); } /* No trailing commas on %U-line */ fprintf(fp,","); pl += 1; if(pl >= max_linelen) { return(i-start); } /* Return non-zero to indicate that more terms should be printed. */ } } int ULLIvec_find_pos_of_1st_larger_than_one(ULLI *vec,int veclen) { int pos_of_1st_term_gte_2 = 1; /* For one-based seqs. only. */ while((pos_of_1st_term_gte_2 <= veclen) && (vec[pos_of_1st_term_gte_2] < 2)) { pos_of_1st_term_gte_2++; } if(pos_of_1st_term_gte_2 > veclen) { pos_of_1st_term_gte_2 = 1; } /* Not found, use 1. */ return(pos_of_1st_term_gte_2); } /* Here's our C-version of jacobi-symbol. This one for max. 32-bit numbers. */ int js_ULI(ULI p,ULI q) { ULI s = 0; /* 0 in bit-2 stands for +1, 1 in bit-2 for -1. */ ULI new_p; loop: if(0 == p) { return(p); } if(1 == p) { return(1-(s&2)); } /* Convert 1 in bit-1 to -1, 0 to +1. */ if(p&1) /* We have an odd p. */ { /* If both p & q are 3 mod 4, then the sign changes, otherwise stays same: */ s ^= (p&q); /* Only the bit-1 is significant, others are ignored. */ new_p = q % p; /* Could we have a simple minus here as with Euclid? */ q = p; p = new_p; goto loop; } else /* We have an even p. So (2k/q) = (2/q)*(k/q) */ { /* where (2/q) = 1 if q is +-1 mod 8 and -1 if q is +-3 mod 8. */ /* I.e. sign changes only if q's lower bits are (011) or (101), i.e. if the bit-1 and bit-2 xored yield 1. */ s ^= (q^(q>>1)); /* Thus, this does it. */ p >>= 1; goto loop; } } /* Use this one if you implement, say a Soloway-Strassen primality test, as this is for 64-bit integers. */ int js_ULLI(ULLI p,ULLI q) { ULLI s = 0; /* 0 in bit-2 stands for +1, 1 in bit-2 for -1. */ ULLI new_p; loop: if(0 == p) { return(p); } if(1 == p) { return(1-(s&2)); } /* Convert 1 in bit-1 to -1, 0 to +1. */ if(p&1) /* We have an odd p. */ { /* If both p & q are 3 mod 4, then the sign changes, otherwise stays same: */ s ^= (p&q); /* Only the bit-1 is significant, others are ignored. */ new_p = q % p; /* Could we have a simple minus here as with Euclid? */ q = p; p = new_p; goto loop; } else /* We have an even p. So (2k/q) = (2/q)*(k/q) */ { /* where (2/q) = 1 if q is +-1 mod 8 and -1 if q is +-3 mod 8. */ /* I.e. sign changes only if q's lower bits are (011) or (101), i.e. if the bit-1 and bit-2 xored yield 1. */ s ^= (q^(q>>1)); /* Thus, this does it. */ p >>= 1; goto loop; } } /* Here it is in MIT/GNU Scheme: ;; I hope the compiler is clever enough to see that it is ;; required that p and q are fixnums, and compiles nothing ;; unnecessary. (define (fix:jacobi-symbol p q) (if (not (and (fix:fixnum? p) (fix:fixnum? q) (fix:= 1 (fix:and q 1)))) (error "fix:jacobi-symbol: args must be fixnums, and 2. arg should be odd: " p q ) (let loop ((p p) (q q) (s 0)) ;; 0 in bit-2 stands for +1, 1 in bit-2 for -1. (cond ((fix:zero? p) 0) ((fix:= 1 p) (fix:- 1 (fix:and s 2))) ((fix:= 1 (fix:and p 1)) ;; Odd p ? (loop (fix:remainder q p) p (fix:xor s (fix:and p q))) ) (else ;; It's even. (loop (fix:lsh p -1) q (fix:xor s (fix:xor q (fix:lsh q -1)))) ) ) ) ) ) */ /* Returns the index i of the first point where Sum_{j=1..i} JS(i,n) goes negative, and zero if it doesn't go when checked up to i=k. */ int js_diving_index(ULI n,ULI k) { ULI i; long int s; for(s=0,i=1; i <= k; i++) { s += js_ULI(i,n); /* printf("js_diving_index(%lu,%lu): i=%lu,s=%ld\n",n,k,i,s); */ if(s < 0) { return(i); } } if((0 != s) && (i == n)) { fprintf(stderr, "js_diving_index: Sum of J(1,%lu)..J(n-1,%lu) is not zero: %ld", n,n,s); exit(1); } return(0); } int binwidth(ULLI n) { int i=0; while(0 != n) { i++; n >>= 1; } return(i); } int A000120(ULLI n) { int i=0; while(0 != n) { i += (n&1); n >>= 1; } return(i); } /* This is the characteristic function of A000069, i.e. A000120(n) mod 2 */ int A010060(ULLI n) { int i=0; while(0 != n) { i ^= (n&1); n >>= 1; } return(i); } /* A007814(n) gives the # of trailing zeros, A007814(n+1) gives #trailing ones. */ int A007814(ULLI n) { int i=0; while((0 == (n&1)) && (0 != n)) { i++; n >>= 1; } return(i); } char *w6d(char *tb,int n) { sprintf(tb,"%06u",n); return(tb); } void vec_sum_checker(FILE *fp,int veclen,int offset, int Anum_sum,ULLI *sumvec, int Anum1summand,ULLI *summand1vec, int Anum2summand,ULLI *summand2vec) { int i,matched; char tb1[81] = { 'A' }, tb2[81] = { 'A' }, tb3[81] = { 'A' }; char *Astr1summand = (w6d(tb1+1,Anum1summand)-1); char *Astr2summand = (w6d(tb2+1,Anum2summand)-1); char *Astr_sum = (w6d(tb3+1,Anum_sum)-1); for(i=offset, matched=0; i <= veclen; i++) { if((summand1vec[i] + summand2vec[i]) == sumvec[i]) { matched++; } else { fprintf(fp,"%s[%u] != (%s[%u]+%s[%u]), i.e. ", Astr_sum,i, Astr1summand,i, Astr2summand,i); fprint_ulli(fp,sumvec[i]); fprintf(fp," != ("); fprint_ulli(fp,summand1vec[i]); fprintf(fp,"+"); fprint_ulli(fp,summand2vec[i]); fprintf(fp,")\n"); } } fprintf(fp,"%s matched %s+%s in %u positions.\n", Astr_sum,Astr1summand,Astr2summand,matched); } /* BISECT a vector vec[1..veclen] in place. parity = 0: take even-positioned terms: 2,4,6,8,... -> 1,2,3,4,... = 1: take odd-positioned terms: 1,3,5,7,... -> 1,2,3,4,... */ void bisect(ULLI *vec,int veclen,int parity) { int i, offset = 1; /* Now must always be 1, as I'm so lazy now. */ for(i=offset; i <= veclen; i++) { if(parity == (i&1)) { vec[parity+(i>>1)] = vec[i]; } } } #define OEIS_S_T_U_LINE_MAXLEN 64 void output_OEIS_sequence(FILE *fp,int Anum, ULLI *vec,int veclen, int offset_printed, char *name, char *author_info, char *datestr, char *Y_line, char *extra_H_link) { char tb[81] = { 'A' }; char *Astr = (w6d(tb+1,Anum)-1); int pos_of_1st_term_gte_2 = ULLIvec_find_pos_of_1st_larger_than_one(vec,veclen); int printed_only_up_to_nth_term = 0; int sec_printed_only_up_to_nth_term = 0; int upto_n = veclen; int offset = 1; fprintf(fp,"%%I %s\n",Astr); /* Old way: all the terms to %S-line: { fprintf(fp,"%%S %s ",Astr); fprint_ULLI_vector(fp,vec,offset,veclen); } */ { fprintf(fp,"%%S %s ",Astr); printed_only_up_to_nth_term = fprint_ULLI_vector_in_pieces(fp,vec,offset,veclen, OEIS_S_T_U_LINE_MAXLEN,0); fprintf(fp,"\n"); } if(printed_only_up_to_nth_term > 0) /* Continue onto the %T -line ? */ { fprintf(fp,"%%T %s ",Astr); sec_printed_only_up_to_nth_term = fprint_ULLI_vector_in_pieces(fp,vec+printed_only_up_to_nth_term, offset, upto_n-printed_only_up_to_nth_term, OEIS_S_T_U_LINE_MAXLEN,0); fprintf(fp,"\n"); } if(sec_printed_only_up_to_nth_term > 0) /* Continue onto the %U -line ? */ { printed_only_up_to_nth_term += sec_printed_only_up_to_nth_term ; fprintf(fp,"%%U %s ",Astr); fprint_ULLI_vector_in_pieces(fp,vec+printed_only_up_to_nth_term,offset, upto_n-printed_only_up_to_nth_term, OEIS_S_T_U_LINE_MAXLEN,1); fprintf(fp,"\n"); } fprintf(fp,"%%N %s %s\n",Astr,name); /* Name should end with period. */ fprintf(fp,"%%Y %s %s\n",Astr,Y_line); fprintf(fp,"%%H %s A. Karttunen, J. Moyer: C-program for computing the initial terms of this sequence\n", Astr); if(NULL != extra_H_link) { fprintf(fp,"%%H %s %s\n",Astr,extra_H_link); } fprintf(fp,"%%K %s nonn\n",Astr); fprintf(fp,"%%O %s %u,%u\n",Astr,offset_printed,pos_of_1st_term_gte_2); fprintf(fp,"%%A %s %s, %s\n", Astr, author_info, datestr); fprintf(fp,"\n"); fflush(fp); } /**********************************************************************/ /* main follows. */ /**********************************************************************/ /* Max exp-value 63 is surely enough. Nobody will compute up to that many terms in the foreseeable future. */ int main(int argc, char *argv[]) { int expi; int max_terms_collected; ULLI start, stop; char *progname = argv[0]; char *s; int only_4k3_extension = 0; char *extra_H_link = "Index entries for sequences related to " "occurrences of various subsets of primes in range ]2^n,2^(n+1)]"; /* We should then have an index-entry like: primes, various subsets in range ]2^n,2^(n+1), sequences related to (start):
*/ /* One might wonder why I (AK) don't use getopt as jrm did, but the reason is that I never have... */ arg_loop: if(NULL != (s = *++argv)) { if('-' == *s) { switch(*(s+1)) { case 'd': case 'e': { if('e' == *(s+1)) { only_4k3_extension = 1; } if(!*(s+2)) { ++argv; if(!(*argv) || !isdigit(**(argv))) { numeric_required: fprintf(stderr, "%s: Option -%c requires a numeric parameter!\n", progname,*(s+1)); goto usage; } else { glob_dyckness_checked_only_up_to_n = atoi(*argv); } } else /* Something following directly after -d */ { if(!isdigit(*(s+2))) { goto numeric_required; } glob_dyckness_checked_only_up_to_n = atoi(s+2); } goto arg_loop; } default: { fprintf(stderr,"%s: Unknown option %s !\n",progname,s); goto usage; break; } } } expi = atoi(*argv); if((expi < 1) || (expi > 63)) { usage: fprintf(stderr, "Usage: %s [-d num] exponent, where the exponent is in range [1,63]\n", progname); exit(1); } start = 3; /* stop = power_of_2(expi+1)-1; */ stop = power_of_2(expi+1)+1; /* Because we search twin primes also. */ } else { goto usage; } precompute_fibos_to_vector(vecA000045,COMPUTE_FIBOS_UP_TO); precompute_fibbinaries_to_vector(vecA003714,127); max_terms_collected = 101; if(only_4k3_extension) { iterate_over_4k_plus3(glob_dyckness_checked_only_up_to_n, max_terms_collected); output_OEIS_sequence(stdout, 95090,vecA095090, glob_dyckness_checked_only_up_to_n, 1, "Number of 4k+3 integers in range ]2^n,2^(n+1)]" " whose Jacobi-vector is a Motzkin-path (A095100).", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = (2^(n-2))-A095091(n) for n > 1. Cf. A095092.", NULL ); output_OEIS_sequence(stdout, 95100,vecA095100,vecA095100[0], 1, "Integers n of the form 4k+3 for which all sums Sum_{i=1..u} J(i/n)" " (with u ranging from 1 to (n-1)) are nonnegative," " where J(i/n) is Jacobi symbol of i and n." "\n%C A095100 Integers whose Jacobi-vector forms" " a valid Motzkin-path.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = 4*A095274(n)+3." " Subset: A095102." " Complement of A095101 in A004767. Cf. A095090.", NULL ); output_OEIS_sequence(stdout, 95091,vecA095091, glob_dyckness_checked_only_up_to_n, 1, "Number of 4k+3 integers in range ]2^n,2^(n+1)]" " whose Jacobi-vector is not a valid Motzkin-path (A095101).", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = (2^(n-2))-A095090(n) for n > 1. Cf. A095093.", NULL ); output_OEIS_sequence(stdout, 95101,vecA095101,vecA095101[0], 1, "Integers n of the form 4k+3 for which some of the sums" " Sum_{i=1..u} J(i/n) (with u ranging from 1 to (n-1)) is negative," " where J(i/n) is Jacobi symbol of i and n." "\n%C A095100 Integers whose Jacobi-vector does not form" " a valid Motzkin-path.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "A095271 gives the diving indices. a(n) = 4*A095275(n)+3." " Subset: A095103." " Complement of A095100 in A004767. Cf. A095091.", NULL ); output_OEIS_sequence(stdout, 95109,vecA095109, glob_dyckness_checked_only_up_to_n, 1, "Sum of diving indices of all 4k+3 integers in range ]2^n,2^(n+1)]." "\n%C A095109 Diving index is explained at A095269.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095110.", NULL ); output_OEIS_sequence(stdout, 95110,vecA095110, glob_dyckness_checked_only_up_to_n, 1, "Sum of max. Motzkin path prefix-lengths of all 4k+3 integers" " in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095270, A095109.", NULL ); output_OEIS_sequence(stdout, 95269,vecA095269,vecA095269[0], 0, "Diving index of 4n+3." "\n%C A095269 Diving index of an odd number n is the first integer u > 1" " where Sum_{i=1..u} J(i/n) results -1, and zero if never." " Here J(i/n) is Jacobi symbol of i and n, which reduces to" " a Legendre symbol L(i/n) when n is a prime.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n)=A095270(n)+1 modulo A004767(n)." " Cf. A095109, A095271 (same sequence with zeros removed).", NULL ); output_OEIS_sequence(stdout, 95270,vecA095270,vecA095270[0], 1, "Length of max. Motzkin path prefix in the Jacobi-vector of 4n+3.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n)=A095269(n)-1 modulo A004767(n)." " Cf. A095110, A095105.", NULL ); output_OEIS_sequence(stdout, 95271,vecA095271,vecA095271[0], 1, "Diving index of A095101(n)." "\n%F A095271 a(n) = A095269(A095275(n)). See comments at A095269.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095108.", NULL ); output_OEIS_sequence(stdout, 95274,vecA095274,vecA095274[0], 0, "a(n) = (A095100(n)-3)/4.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095275. Subset: A095272.", NULL ); output_OEIS_sequence(stdout, 95275,vecA095275,vecA095275[0], 0, "a(n) = (A095101(n)-3)/4.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095274. Subset: A095273.", NULL ); exit(1); } compute_primes(start,stop,max_terms_collected); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95005,vecA095005,95006,vecA095006); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95007,vecA095007,95008,vecA095008); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95013,vecA095013,95014,vecA095014); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95015,vecA095015,95016,vecA095016); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95019,vecA095019,95054,vecA095054); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95020,vecA095020,95055,vecA095055); vec_sum_checker(stdout,expi,1, 95013,vecA095013,95009,vecA095009,95012,vecA095012); vec_sum_checker(stdout,expi,1, 95014,vecA095014,95010,vecA095010,95011,vecA095011); vec_sum_checker(stdout,expi,1, 95054,vecA095054,95018,vecA095018,95020,vecA095020); vec_sum_checker(stdout,expi,1, 95055,vecA095055,95018,vecA095018,95019,vecA095019); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95063,vecA095063,95064,vecA095064); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95060,vecA095060,95061,vecA095061); vec_sum_checker(stdout,expi,1, 95060,vecA095060,95062,vecA095062,95067,vecA095067); vec_sum_checker(stdout,expi,1, 95061,vecA095061,95066,vecA095066,95069,vecA095069); vec_sum_checker(stdout,expi,1, 95062,vecA095062,95065,vecA095065,95068,vecA095068); vec_sum_checker(stdout,expi,1, 95008,vecA095008,95092,vecA095092,95093,vecA095093); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95094,vecA095094,95095,vecA095095); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95290,vecA095290,95291,vecA095291); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95292,vecA095292,95293,vecA095293); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95294,vecA095294,95295,vecA095295); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95296,vecA095296,95297,vecA095297); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95332,vecA095332,95333,vecA095333); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95334,vecA095334,95335,vecA095335); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95326,vecA095326,95327,vecA095327); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95328,vecA095328,95329,vecA095329); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95330,vecA095330,95331,vecA095331); vec_sum_checker(stdout,expi,1, 36378,vecA036378,95324,vecA095324,95325,vecA095325); output_OEIS_sequence(stdout, 45,vecA000045, max_terms_collected, 1, "Fibonacci numbers: F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1, F(2) = 1, ...", "njas", "", "HERE JUST FOR CHECKING!", NULL ); output_OEIS_sequence(stdout, 3714,vecA003714, max_terms_collected, 1, "Fibbinary numbers", "njas", "", "HERE JUST FOR CHECKING!", NULL ); output_OEIS_sequence(stdout, 36378,vecA036378, expi, 1, "Number of primes p such that 2^n < p < 2^(n+1).", "Labos E. (labos(AT)ana1.sote.hu)", "May 13 2004", "a(n) = A095005(n)+A095006(n) = A095007(n) + A095008(n)" " = A095013(n) + A095014(n)" " = A095015(n) + A095016(n) (for n > 1)" " = A095021(n)+A095022(n)+A095023(n)+A095024(n)" /* " = A095019(n)+A095020(n) + (if n is odd) A095018((n+1)/2)" */ " = A095019(n)+A095054(n)" " = A095020(n)+A095055(n)" " = A095060(n)+A095061(n)" " = A095063(n)+A095064(n)" " = A095094(n)+A095095(n). Cf. A095354.", extra_H_link ); output_OEIS_sequence(stdout, 95005,vecA095005, expi, 1, "Number of odious primes (A027697) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095006(n).", extra_H_link ); output_OEIS_sequence(stdout, 95006,vecA095006, expi, 1, "Number of evil primes (A027699) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095005(n).", extra_H_link ); output_OEIS_sequence(stdout, 27697,vecA027697,vecA027697[0], 1, "Odious primes: primes with odd number of 1's in binary expansion.", "njas", "", "Complement of A027699 in A000040." " Union of A091206\{3} and odious members of A091209." " Cf. A095005.", NULL ); output_OEIS_sequence(stdout, 27699,vecA027699,vecA027699[0], 1, "Evil primes: primes with even number of 1's in binary expansion.", "njas", "", "Complement of A027697 in A000040." " Cf. A095006.", NULL ); output_OEIS_sequence(stdout, 95007,vecA095007, expi, 1, "Number of 4k+1 primes (A002144) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095008(n) = A095009(n)+A095011(n).", extra_H_link ); output_OEIS_sequence(stdout, 95008,vecA095008, expi, 1, "Number of 4k+3 primes (A002145) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095007(n) = A095010(n)+A095012(n)" " = A095092(n)+,A095093(n).", extra_H_link ); /* Cf. A091126, A091127, A091128, A091129. */ output_OEIS_sequence(stdout, 95009,vecA095009, expi, 1, "Number of 8k+1 primes (A007519) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095013(n)-A095012(n) = A095007(n)-A095011(n). " "Cf. A091126.", extra_H_link ); output_OEIS_sequence(stdout, 95010,vecA095010, expi, 1, "Number of 8k+3 primes (A007520) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095014(n)-A095011(n) = A095008(n)-A095012(n). " "Cf. A091127.", extra_H_link ); output_OEIS_sequence(stdout, 95011,vecA095011, expi, 1, "Number of 8k+5 primes (A007521) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095014(n)-A095010(n). Cf. A091128.", extra_H_link ); output_OEIS_sequence(stdout, 95012,vecA095012, expi, 1, "Number of 8k+7 primes (A007522) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095013(n)-A095009(n). Cf. A091129.", extra_H_link ); output_OEIS_sequence(stdout, 95013,vecA095013, expi, 1, "Number of 8k+-1 primes (A001132) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095014(n) = A095009(n)+A095012(n).", extra_H_link ); output_OEIS_sequence(stdout, 95014,vecA095014, expi, 1, "Number of 8k+-3 primes (A003629) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095013(n) = A095010(n)+A095011(n).", extra_H_link ); output_OEIS_sequence(stdout, 95015,vecA095015, expi, 1, "Number of 6k+1 primes (A002476) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095016(n) (apart the initial term).", extra_H_link ); output_OEIS_sequence(stdout, 95016,vecA095016, expi, 1, "Number of 6k+5 primes (A007528) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095015(n) (apart the initial term).", extra_H_link ); output_OEIS_sequence(stdout, 95017,vecA095017, expi, 1, "Number of lesser twin primes (A001359) in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095016, A036378.", extra_H_link ); output_OEIS_sequence(stdout, 95021,vecA095021, expi, 1, "Number of 5k+1 primes (A030430) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A036378.", extra_H_link ); output_OEIS_sequence(stdout, 95022,vecA095022, expi, 1, "Number of 5k+2 primes (A030432) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A036378.", extra_H_link ); output_OEIS_sequence(stdout, 95023,vecA095023, expi, 1, "Number of 5k+3 primes (A030431) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A036378.", extra_H_link ); output_OEIS_sequence(stdout, 95024,vecA095024, expi, 1, "Number of 5k+4 primes (A030433) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A036378.", extra_H_link ); /* Neil doesn't like aerated sequences too much, so we bisect the sequence, by taking the odd-positioned terms and instead of: %S A095018 0,0,0,0,2,0,4,0,17,0,28,0,189,0,531,0,1990,0,5747,0,23902,0,76658, we should get: %S A095018 0,0,2,4,17,28,189,531,1990,5747,23902,76658,291478,,982793, %T A095018 3677580,13214719,49161612 */ bisect(vecA095018,expi,1); output_OEIS_sequence(stdout, 95018,vecA095018, ((expi+1)>>1), 1, "Number of binarily balanced primes (A066196) in range ]2^(2n-1),2^2n]." "\n%e A095018 Only primes in range ]2^5,2^6] with equal numbers of" " ones and zeros in their binary expansion are" " 37 (in binary 100101) and 41 (in binary 101011)" " thus a(3)=2.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095005-A095006, A095052-A095053.", extra_H_link ); /* He we bisect the sequence, by taking the even-positioned terms and instead of: %S A095052 0,0,0,1,0,3,0,10,0,25,0,78,0,283,0,906,0,3044,0,10920,0,37920,0, we should get: %S A095052 0,1,3,10,25,78,283,906,3044,10920,37920,135182,487555,1764216, %T A095052 6415902,23585285 */ bisect(vecA095052,expi,0); output_OEIS_sequence(stdout, 95052,vecA095052, (expi>>1), /* Now the sequence is only half as long. */ 1, "Number of primes with number of 0-bits equal to one plus number of 1-bits" " (A095072)" " in range ]2^2n,2^(2n+1)]." "\n%e A095052 In range ]2^4,2^5] 17 (10001 in binary) is only such prime" " thus a(2)=1.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); bisect(vecA095053,expi,0); /* Do the same for this. */ output_OEIS_sequence(stdout, 95053,vecA095053, (expi>>1), /* Now the sequence is only half as long. */ 1, "Number of primes with number of 1-bits equal to one plus number 0-bits" " (A095073)" " in range ]2^2n,2^(2n+1)]." "\n%e A095053 In range ]2^2,2^3] 5 (101 in binary) is only such prime" " thus a(1)=1, and similarly, in range ]2^4,2^5] 19 (10011 in binary)" " is also unique in that respect, thus a(2)=1 as well.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); output_OEIS_sequence(stdout, 95056,vecA095056, expi, 1, "Number of primes with exactly three 1-bits (A081091)" " in range ]2^n,2^(n+1)].", "Labos E. (labos(AT)ana1.sote.hu) & " "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); output_OEIS_sequence(stdout, 95057,vecA095057, expi, 1, "Number of primes with four 1-bits (A095077) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); output_OEIS_sequence(stdout, 95058,vecA095058, expi, 1, "Number of primes with a single 0-bit (A095078) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); output_OEIS_sequence(stdout, 95059,vecA095059, expi, 1, "Number of primes with two 0-bits (A095079) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); /* Then a few prime-sequences themselves: */ output_OEIS_sequence(stdout, 95072,vecA095072, vecA095072[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion the number of 0-bits is one more" " than the number of 1-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A031444. Subset of A095071." " Cf. A095052.", NULL ); output_OEIS_sequence(stdout, 95073,vecA095073, vecA095073[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion the number of 1-bits is one more" " than the number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A031448. Subset of A095070." " Cf. A095053.", NULL ); output_OEIS_sequence(stdout, 95077,vecA095077, vecA095077[0], /* Contains the count of collected primes. */ 1, "Primes with exactly four 1-bits in their binary expansion.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Subset of A027699. " "Differs from A085448 first time at n=19, where a(n)=337, " "while A085448 continues from there with 311, whose binary expansion " "has six 1-bits, not four. Cf. A095057.", NULL ); output_OEIS_sequence(stdout, 95078,vecA095078, vecA095078[0], /* Contains the count of collected primes. */ 1, "Primes with a single 0-bit in their binary expansion.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A030130. Cf. A095058.", NULL ); output_OEIS_sequence(stdout, 95079,vecA095079, vecA095079[0], /* Contains the count of collected primes. */ 1, "Primes with two 0-bits in their binary expansion.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", /* "Intersect of A000040 & A0xxxxx. " */ "Cf. A095059.", NULL ); output_OEIS_sequence(stdout, 95060,vecA095060, expi, 1, "Number of fibeven primes (A095080) in range ]2^n,2^(n+1)]." "\n%C A095060 As expected, the ratio of a(n)/A036378(n) seems to approach" " (sqrt(5)-1)/2 (= 0.6180339887...): 1, 1, 1, 0.6, 0.42857, 0.69231, 0.69565," " 0.5814, 0.66667, 0.60584, 0.58824, 0.61638, 0.61927, 0.60484, 0.61551," " 0.61569, 0.61289, 0.61893, 0.61693, 0.61813, 0.61859, 0.61824, 0.61858," " 0.61727, 0.6178, 0.61829, 0.61795, 0.61816, 0.61804, 0.61808, 0.61804," " 0.61803, 0.61805", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095061(n) = A095062(n)+A095067(n).", extra_H_link ); output_OEIS_sequence(stdout, 95080,vecA095080,vecA095080[0], 1, "Fibeven primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with zero.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A022342. Union of A095082 & A095087." " Cf. A095060, A095081.", NULL ); output_OEIS_sequence(stdout, 95061,vecA095061, expi, 1, "Number of fibodd primes (A095081) in range ]2^n,2^(n+1)]." "\n%C A095061 As expected, the ratio of a(n)/A036378(n) seems to approach" " 1-((sqrt(5)-1)/2) (= 0.381966011250...): 0, 0, 0, 0.4, 0.57143, 0.30769," " 0.30435, 0.4186, 0.33333, 0.39416, 0.41176, 0.38362, 0.38073, 0.39516," " 0.38449, 0.38431, 0.38711, 0.38107, 0.38307, 0.38187, 0.38141, 0.38176," " 0.38142, 0.38273, 0.3822, 0.38171, 0.38205, 0.38184, 0.38196, 0.38192," " 0.38196, 0.38197, 0.38195", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095060(n) = A095066(n)+A095069(n).", extra_H_link ); output_OEIS_sequence(stdout, 95081,vecA095081,vecA095081[0], 1, "Fibodd primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with one.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A003622. Union of A095086 & A095089." " Cf. A095061, A095080, A095281.", NULL ); output_OEIS_sequence(stdout, 95062,vecA095062, expi, 1, "Number of fib00 primes (A095082) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095060(n)-A095067(n) = A095065(n)+A095068(n).", extra_H_link ); output_OEIS_sequence(stdout, 95082,vecA095082,vecA095082[0], 1, "Fib00 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with two zeros.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095062. Intersect of A000040 & A026274. Union of A095085 & A095088.", NULL ); output_OEIS_sequence(stdout, 95065,vecA095065, expi, 1, "Number of fib000 primes (A095085) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095062(n)-A095068(n). Cf. A095066-A095067.", extra_H_link ); output_OEIS_sequence(stdout, 95085,vecA095085,vecA095085[0], 1, "Fib000 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with three zeros.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095097. Cf. A095065.", NULL ); output_OEIS_sequence(stdout, 95066,vecA095066, expi, 1, "Number of fib001 primes (A095086) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095061(n)-A095069(n). Cf. A095065 & A095067.", extra_H_link ); output_OEIS_sequence(stdout, 95086,vecA095086,vecA095086[0], 1, "Fib001 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with two zeros and final 1.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095098. Cf. A095066.", NULL ); output_OEIS_sequence(stdout, 95067,vecA095067, expi, 1, "Number of fib010 primes (A095087) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095060(n)-A095062(n).", extra_H_link ); output_OEIS_sequence(stdout, 95087,vecA095087,vecA095087[0], 1, "Fib010 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with zero, one and zero.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A035336. Cf. A095067.", NULL ); output_OEIS_sequence(stdout, 95068,vecA095068, expi, 1, "Number of fib100 primes (A095088) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095062(n)-A095065(n).", extra_H_link ); output_OEIS_sequence(stdout, 95088,vecA095088,vecA095088[0], 1, "Fib100 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends with one and two final zeros.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A035337. Cf. A095068.", NULL ); output_OEIS_sequence(stdout, 95069,vecA095069, expi, 1, "Number of fib101 primes (A095089) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095061(n)-A095066(n).", extra_H_link ); output_OEIS_sequence(stdout, 95089,vecA095089,vecA095089[0], 1, "Fib101 primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " ends as one, zero, one.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095099. Cf. A095069.", NULL ); output_OEIS_sequence(stdout, 95063,vecA095063, expi, 1, "Number of fibodious primes (A095083) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095064(n).", extra_H_link ); output_OEIS_sequence(stdout, 95083,vecA095083,vecA095083[0], 1, "Fibodious primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " contains an odd number of 1-fibits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A020899. Cf. A095084, A095063.", NULL ); output_OEIS_sequence(stdout, 95064,vecA095064, expi, 1, "Number of fibevil primes (A095084) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095063(n).", extra_H_link ); output_OEIS_sequence(stdout, 95084,vecA095084,vecA095084[0], 1, "Fibevil primes, i.e. primes p whose Zeckendorf-expansion A014417(p)" " contains an even number of 1-fibits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095096. Cf. A095083, A095064.", NULL ); output_OEIS_sequence(stdout, 95092,vecA095092, glob_dyckness_checked_only_up_to_n, 1, "Number of 4k+3 primes whose Legendre-vector is a Dyck-path (A095102)" " in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095008(n)-A095093(n). Cf. A095090.", extra_H_link ); output_OEIS_sequence(stdout, 95102,vecA095102,vecA095102[0], 1, "Odd primes p for which all sums Sum_{i=1..u} L(i/p) (with u ranging from 1" " to (p-1)) are nonnegative, where L(i/p) is Legendre symbol of i and p," " defined to be 1 if i is a quadratic residue (mod p) and -1" " if i is a quadratic non-residue (mod p)." "\n%C A095102 All 4k+3 primes whose Legendre-vector (cf. A055094) forms" " a valid Dyck-path (cf. A014486).", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095100. Subset of A080114 (see comments there)." " Complement of A095103 in A002145. a(n) = 4*A095272(n)+3. Cf. A095092.", NULL ); output_OEIS_sequence(stdout, 95093,vecA095093, glob_dyckness_checked_only_up_to_n, 1, "Number of 4k+3 primes whose Legendre-vector is not Dyck-path (A095103)" " in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095008(n)-A095092(n).", extra_H_link ); output_OEIS_sequence(stdout, 95103,vecA095103,vecA095103[0], 1, "4k+3 primes whose Legendre-vector is not valid Dyck-path.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A095101." " Complement of A095102 in A002145. Diving indices: A095108." " a(n) = 4*A095273(n)+3." " Cf. also A095093.", NULL ); output_OEIS_sequence(stdout, 95094,vecA095094, glob_dyckness_checked_only_up_to_n, 1, "Number of A080114-primes in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095095(n).", extra_H_link ); output_OEIS_sequence(stdout, 80114,vecA080114,vecA080114[0], 1, "Odd primes p for which all sums Sum_{i=1..u} L(i/p) (with u ranging from 1" " to (p-1)/2) are nonnegative, where L(i/p) is Legendre symbol of i and p," " which is defined to be 1 if i is a quadratic residue (mod p) and -1" " if i is a quadratic non-residue (mod p).", /* "Primes whose Legendre-vector's first half is a valid Dyck-path.", */ "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Feb 11 2003", "Intersect of A000040 & A0xxxxx. Subset: A095102." " Complement of A080115 in A000040. Cf. A095094.", NULL ); output_OEIS_sequence(stdout, 95095,vecA095095, glob_dyckness_checked_only_up_to_n, 1, "Number of A080115-primes in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A036378(n)-A095094(n).", extra_H_link ); output_OEIS_sequence(stdout, 80115,vecA080115,vecA080115[0], 1, "Primes not in A080114.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Feb 11 2003", /* "Intersect of A000040 & A0xxxxx." */ " Complement of A080114 in A000040. Cf. A095095.", NULL ); output_OEIS_sequence(stdout, 95104,vecA095104,vecA095104[0], 1, "Diving index of the nth 4k+3 prime (A002145(n))." "\n%C A095104 Diving index of an odd number n is the first integer u > 1" " where Sum_{i=1..u} J(i/n) results -1, and zero if never." " Here J(i/n) is Jacobi symbol of i and n, which reduces to" " a Legendre symbol L(i/n) when n is a prime.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n)=A095105(n)+1 modulo A002145(n)." " Cf. A095106, A095108 (same sequence with zeros removed), A095269.", NULL ); output_OEIS_sequence(stdout, 95108,vecA095108,vecA095108[0], 1, "Diving index of the nth diving 4k+3 prime (A095103(n)).", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Non-zero terms of A095104. Cf. A095271.", NULL ); output_OEIS_sequence(stdout, 95105,vecA095105,vecA095105[0], 1, "Length of max. Dyck path prefix in the Legendre-vector of" " the nth 4k+3 prime (A002145(n)).", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n)=A095104(n)-1 modulo A002145(n)." " Cf. A095107, A095270.", NULL ); output_OEIS_sequence(stdout, 95106,vecA095106, glob_dyckness_checked_only_up_to_n, 1, "Sum of diving indices of all 4k+3 primes in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095104, A095107, A095109.", NULL ); output_OEIS_sequence(stdout, 95107,vecA095107, glob_dyckness_checked_only_up_to_n, 1, "Sum of max Dyck path prefix lengths of all 4k+3 primes" " in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095105, A095106, A095110.", NULL ); output_OEIS_sequence(stdout, 95272,vecA095272,vecA095272[0], 1, "a(n) = (A095102(n)-3)/4.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095273 in A095278, subset of A095274.", NULL ); output_OEIS_sequence(stdout, 95273,vecA095273,vecA095273[0], 1, "a(n) = (A095103(n)-3)/4.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095272 in A095278, subset of A095275.", NULL ); /* Some new ones June 3 2004. */ output_OEIS_sequence(stdout, 95280,vecA095280,vecA095280[0], 1, "Lower Wythoff Primes, i.e. primes in A000201." "\n%C A095280 Contains all primes p whose Zeckendorf-expansion" " A014417(p) ends with an even number of 0's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Intersect of A000040 & A000201. Complement of A095281 in A000040." " Cf. A095080, A095083, A095084, A095290.", NULL ); output_OEIS_sequence(stdout, 95290,vecA095290, expi, 1, "Number of Lower Wythoff Primes (A095280) in range ]2^n,2^(n+1)]." "\n%C A095090 As expected, the ratio of a(n)/A036378(n) seems to approach" " (sqrt(5)-1)/2 (= 0.6180339887...): 1, 0, 0.5, 0.6, 0.714286, 0.615385," " 0.608696, 0.697674, 0.533333, 0.627737, 0.635294, 0.622845, 0.620413," " 0.630893, 0.620792, 0.617796, 0.618848, 0.619961, 0.617445, 0.617713," " 0.618181, 0.618323, 0.617789, 0.618717, 0.618428, 0.618142, 0.618057," " 0.617987, 0.618105, 0.617965, 0.618065, 0.618053, 0.618047", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095291(n). Cf. A095060, A095291.", extra_H_link ); output_OEIS_sequence(stdout, 95281,vecA095281,vecA095281[0], 1, "Upper Wythoff Primes, i.e. primes in A001950." "\n%C A095281 Contains all primes p whose Zeckendorf-expansion" " A014417(p) ends with an odd number of 0's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Intersect of A000040 & A001950. Complement of A095280 in A000040." " Cf. A095081, A095083, A095084, A095290.", NULL ); output_OEIS_sequence(stdout, 95291,vecA095291, expi, 1, "Number of Upper Wythoff Primes (A095281) in range ]2^n,2^(n+1)]." "\n%C A095291 As expected, the ratio of a(n)/A036378(n) seems to approach" " 1-((sqrt(5)-1)/2) (= 0.381966011250...): 0, 1, 0.5, 0.4, 0.285714," " 0.384615, 0.391304, 0.302326, 0.466667, 0.372263, 0.364706, 0.377155," " 0.379587, 0.369107, 0.379208, 0.382204, 0.381152, 0.380039, 0.382555," " 0.382287, 0.381819, 0.381677, 0.382211, 0.381283, 0.381572, 0.381858," " 0.381943, 0.382013, 0.381895, 0.382035, 0.381935, 0.381947, 0.381953" "\n%C A095291 Also expected, the ratio a(n)/A095061(n) seems to approach 1:" " 1, 0, 0, 1, 0.5, 1.25, 1.28571, 0.72222, 1.4, 0.94444, 0.88571, 0.98315," " 0.99699, 0.93407, 0.98627, 0.99453, 0.98462, 0.9973, 0.99865, 1.0011," " 1.00108, 0.99979, 1.00208, 0.99622, 0.99835, 1.00039, 0.99973, 1.00046," " 0.99983, 1.00031, 0.99994, 0.99994, 1.00001", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095290(n). Cf. A095061, A095290.", extra_H_link ); output_OEIS_sequence(stdout, 95282,vecA095282,vecA095282[0], 1, "Primes whose binary-expansion ends with an even number of 1's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Intersect of A000040 & (complement of A079523)." " Complement of A095283 in A000040." " Cf. A027699, A095292.", NULL ); output_OEIS_sequence(stdout, 95292,vecA095292, expi, 1, "Number of A095282-primes in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095293(n). Cf. A095006.", extra_H_link ); output_OEIS_sequence(stdout, 95283,vecA095283,vecA095282[0], 1, "Primes whose binary-expansion ends with an odd number of 1's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Intersect of A000040 & A079523." " Complement of A095282 in A000040." " Cf. A027697, A095293.", NULL ); output_OEIS_sequence(stdout, 95293,vecA095293, expi, 1, "Number of A095283-primes in range ]2^n,2^(n+1)]." "\n%C A095293 As expected, the ratio a(n)/A095292(n) seems to approach 2:" " 0, 0, 1, 4, 1.33333, 2.25, 1.55556, 2.07143, 2.26087, 1.91489, 1.89773," " 2.05263, 1.95593, 1.98519, 2.01793, 1.95344, 2.00924, 1.99633, 1.99287," " 2.0083, 2.00075, 1.99746, 1.99841, 1.99971, 2.00034, 2.00001, 2.00018," " 1.99977, 1.99971, 1.99997, 2.00004, 1.99995, 2.00003", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095292(n). Cf. A095005.", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95320,vecA095320, vecA095320[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > number of 0-bits minus 3." "\n%C A095320 Differs from primes (A000040) first time at n=55," " where a(55)=263, while A000040(55)=257, as 257 whose binary" " expansion is 100000001, with 2 1-bits and 7 0-bits is the first" " prime excluded from this sequence." " Note that 129 (10000001 in binary, 2 1-bits and 6 0-bits) is" " not prime.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095321 in A000040. Subset: A095316." "A095330.", NULL ); output_OEIS_sequence(stdout, 95330,vecA095330, expi, 1, "Number of A095320-primes in range ]2^n,2^(n+1)]." "\n%C A095330 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 1, 1, 1, 1," " 0.976744, 0.946667, 0.890511, 0.945098, 0.887931, 0.904817, 0.876551," " 0.914191, 0.851112, 0.88799, 0.831535, 0.881041, 0.82195, 0.863934," " 0.808416, 0.858898, 0.797191, 0.84356, 0.786657, 0.835979, 0.777517," " 0.825576, 0.769947, 0.819026, 0.76292, 0.81036", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095331(n).", extra_H_link ); output_OEIS_sequence(stdout, 95321,vecA095321, vecA095321[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= number of 0-bits minus 3.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095320 in A000040. Subset of A095317." " Cf. also A095331.", NULL ); output_OEIS_sequence(stdout, 95331,vecA095331, expi, 1, "Number of A095321-primes in range ]2^n,2^(n+1)]." "\n%C A095331 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0, 0, 0, 0," " 0.023256, 0.053333, 0.109489, 0.054902, 0.112069, 0.095183, 0.123449," " 0.085809, 0.148888, 0.11201, 0.168465, 0.118959, 0.17805, 0.136066," " 0.191584, 0.141102, 0.202809, 0.15644, 0.213343, 0.164021, 0.222483," " 0.174424, 0.230053, 0.180974, 0.23708, 0.18964", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095330(n).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95316,vecA095316, vecA095316[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > number of 0-bits minus 2." "\n%C A095316 Differs from primes (A000040) first time at n=32," " where a(32)=139, while A000040(32)=131, as 131 whose binary" " expansion is 10000011, with 3 1-bits and 5 0-bits is the first" " prime excluded from this sequence.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095317 in A000040. Subset of A095320. Subset: A095074." " Cf. also A095326.", NULL ); output_OEIS_sequence(stdout, 95326,vecA095326, expi, 1, "Number of A095316-primes in range ]2^n,2^(n+1)]." "\n%C A095326 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 1, 1, 1," " 0.869565, 0.976744, 0.866667, 0.890511, 0.796078, 0.887931, 0.823394," " 0.876551, 0.785809, 0.851112, 0.769002, 0.831535, 0.750485, 0.82195," " 0.751938, 0.808416, 0.73382, 0.797191, 0.730306, 0.786657, 0.717911," " 0.777517, 0.713512, 0.769947, 0.706327, 0.76292, 0.701421", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095327(n).", extra_H_link ); output_OEIS_sequence(stdout, 95317,vecA095317, vecA095317[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= number of 0-bits minus 2.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095316 in A000040. Subset: A095321. Subset of A095071." " Cf. also A095327.", NULL ); output_OEIS_sequence(stdout, 95327,vecA095327, expi, 1, "Number of A095317-primes in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)" "\n%C A095327 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0, 0, 0," " 0.130435, 0.023256, 0.133333, 0.109489, 0.203922, 0.112069, 0.176606," " 0.123449, 0.214191, 0.148888, 0.230998, 0.168465, 0.249515, 0.17805," " 0.248062, 0.191584, 0.26618, 0.202809, 0.269694, 0.213343, 0.282089," " 0.222483, 0.286488, 0.230053, 0.293673, 0.23708, 0.298579", "Jun 03 2004", "a(n) = A036378(n)-A095326(n).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95074,vecA095074, vecA095074[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion the number of 0-bits is less than" " or equal to number of 1-bits." "\n%C A095074 Differs from primes (A000040) first time at n=7," " where a(7)=19, while A000040(7)=17, as 17 whose binary" " expansion is 10001, with 2 1-bits and 3 0-bits is the first" " prime excluded from this sequence.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095071 in A000040." " Subset of A095316. Subset: A095070." " Differs from A057447 first time at n=18, where a(n)=71," " while A057447(18)=67." " Cf. A095054.", NULL ); output_OEIS_sequence(stdout, 95054,vecA095054, expi, 1, "Number of primes with #0-bits <= #1-bits (A095074) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095020(n) + (if n is odd) A095018((n+1)/2)." "\n%C A095054 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 0.8, 1," " 0.769231, 0.869565, 0.744186, 0.866667, 0.708029, 0.796078, 0.719828," " 0.823394, 0.700993, 0.785809, 0.692415, 0.769002, 0.682246, 0.750485," " 0.673552, 0.751938, 0.667037, 0.73382, 0.660064, 0.730306, 0.652924," " 0.717911, 0.647431, 0.713512, 0.643394, 0.706327, 0.639006, 0.701421", extra_H_link ); output_OEIS_sequence(stdout, 95071,vecA095071, vecA095071[0], /* Contains the count of collected primes. */ 1, "Zero-bit dominant primes, i.e. primes whose binary expansion contains" " more 0's than 1's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095074 in A000040." " Subsets: A095317, A095072. Subset of A095075. Cf. also A095019.", NULL ); output_OEIS_sequence(stdout, 95019,vecA095019, expi, 1, "Number of zero-bit dominant primes (A095071) in range ]2^n,2^(n+1)].", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018." "\n%C A095019 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0.2, 0," " 0.230769, 0.130435, 0.255814, 0.133333, 0.291971, 0.203922, 0.280172," " 0.176606, 0.299007, 0.214191, 0.307585, 0.230998, 0.317754, 0.249515," " 0.326448, 0.248062, 0.332963, 0.26618, 0.339936, 0.269694, 0.347076," " 0.282089, 0.352569, 0.286488, 0.356606, 0.293673, 0.360994, 0.298579", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95070,vecA095070, vecA095070[0], /* Contains the count of collected primes. */ 1, "One-bit dominant primes, i.e. primes whose binary expansion contains" " more 1's than 0's.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Intersect of A000040 & A072600. Complement of A095075 in A000040." " Subset of A095074. Subsets: A095286, A095073. Cf. A095020.", NULL ); output_OEIS_sequence(stdout, 95020,vecA095020, expi, 1, "Number of one-bit dominant primes (A095070) in range ]2^n,2^(n+1)]." "\n%C A095020 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 0.8, 0.714286," " 0.769231, 0.695652, 0.744186, 0.64, 0.708029, 0.686275, 0.719828," " 0.606651, 0.700993, 0.610561, 0.692415, 0.583868, 0.682246, 0.601734," " 0.673552, 0.581618, 0.667037, 0.584595, 0.660064, 0.57642, 0.652924," " 0.578057, 0.647431, 0.573186, 0.643394, 0.571734, 0.639006, 0.568309", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Cf. A095018.", extra_H_link ); output_OEIS_sequence(stdout, 95075,vecA095075, vecA095075[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion the number of 1-bits is less than" " or equal to number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "Complement of A095070 in A000040." " Subset: A095071. Subset of A095287." " Cf. A095055.", NULL ); output_OEIS_sequence(stdout, 95055,vecA095055, expi, 1, "Number of primes with #1-bits <= #0-bits (A095075) in range ]2^n,2^(n+1)]." "\n%C A095055 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0.2, 0.285714," " 0.230769, 0.304348, 0.255814, 0.36, 0.291971, 0.313725, 0.280172," " 0.393349, 0.299007, 0.389439, 0.307585, 0.416132, 0.317754, 0.398266," " 0.326448, 0.418382, 0.332963, 0.415405, 0.339936, 0.42358, 0.347076," " 0.421943, 0.352569, 0.426814, 0.356606, 0.428266, 0.360994, 0.431691", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 01 2004", "a(n) = A095019(n) + (if n is odd) A095018((n+1)/2).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95286,vecA095286, vecA095286[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 1 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095287 in A000040. Subset of A095070. Subset: A095314." " Cf. also A095296.", NULL ); output_OEIS_sequence(stdout, 95296,vecA095296, expi, 1, "Number of A095286-primes in range ]2^n,2^(n+1)]." "\n%C A095296 Ratios a(n)/A036378(n) converge as: 1, 0.5, 1, 0.6," " 0.714286, 0.384615, 0.695652, 0.488372, 0.64, 0.50365, 0.686275," " 0.493534, 0.606651, 0.476427, 0.610561, 0.500963, 0.583868, 0.502795," " 0.601734, 0.496874, 0.581618, 0.498624, 0.584595, 0.498259, 0.57642," " 0.498269, 0.578057, 0.499347, 0.573186, 0.498736, 0.571734, 0.498567," " 0.568309" "\n%C A095296 Ratios a(n)/A095335(n) converge as: 1, 1, 1, 1.5, 1.25," " 0.625, 0.842105, 0.954545, 1.116279, 1.014706, 1.100629, 0.974468," " 0.985102, 0.909953, 0.966562, 1.003861, 0.984008, 1.011245, 1.00445," " 0.987575, 0.991822, 0.994512, 0.988408, 0.993061, 0.99389, 0.9931," " 0.99673, 0.997392, 0.997286, 0.994955, 0.995265, 0.994285, 0.996248", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095297(n). Cf. A095298.", extra_H_link ); output_OEIS_sequence(stdout, 95287,vecA095287, vecA095287[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 1 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095286 in A000040." " Subset: A095075. Subset of A095315." " Cf. also A095297.", NULL ); output_OEIS_sequence(stdout, 95297,vecA095297, expi, 1, "Number of A095287-primes in range ]2^n,2^(n+1)]." "\n%C A095297 Ratios a(n)/A036378(n) converge as: 0, 0.5, 0, 0.4," " 0.285714, 0.615385, 0.304348, 0.511628, 0.36, 0.49635, 0.313725," " 0.506466, 0.393349, 0.523573, 0.389439, 0.499037, 0.416132, 0.497205," " 0.398266, 0.503126, 0.418382, 0.501376, 0.415405, 0.501741, 0.42358," " 0.501731, 0.421943, 0.500653, 0.426814, 0.501264, 0.428266, 0.501433," " 0.431691" "\n%C A095297 Ratios a(n)/A095334(n) converge as: 1, 1, 1, 0.666667," " 0.666667, 1.6, 1.75, 1.047619, 0.84375, 0.985507, 0.833333, 1.026201," "1.023881, 1.098958, 1.057348, 0.996154, 1.023336, 0.98888, 0.993351," "1.012581, 1.011595, 1.005518, 1.016781, 1.006987, 1.008436, 1.006948," "1.004514, 1.002615, 1.003668, 1.00507, 1.006392, 1.005748, 1.004982", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095296(n). Cf. A095298.", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95314,vecA095314, vecA095314[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 2 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095315 in A000040. Subset of A095286. Subset: A095318." " Cf. also A095334.", NULL ); output_OEIS_sequence(stdout, 95334,vecA095334, expi, 1, "Number of A095314-primes in range ]2^n,2^(n+1)]." "\n%C A095334 Ratios a(n)/A036378(n) converge as: 0, 0.5, 0, 0.6," " 0.428571, 0.384615, 0.173913, 0.488372, 0.426667, 0.50365, 0.376471," " 0.493534, 0.384174, 0.476427, 0.368317, 0.500963, 0.406642, 0.502795," " 0.400932, 0.496874, 0.413586, 0.498624, 0.408549, 0.498259, 0.420036," " 0.498269, 0.420047, 0.499347, 0.425255, 0.498736, 0.425546, 0.498567," " 0.429551" "\n%C A095334 Ratios a(n)/A095297(n) converge as: 1, 1, 1, 1.5, 1.5," " 0.625, 0.571429, 0.954545, 1.185185, 1.014706, 1.2, 0.974468," " 0.976676, 0.909953, 0.945763, 1.003861, 0.977197, 1.011245, 1.006694," " 0.987575, 0.988538, 0.994512, 0.983496, 0.993061, 0.991634, 0.9931," " 0.995506, 0.997392, 0.996345, 0.994955, 0.993649, 0.994285, 0.995042", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095335(n). Cf. A095298.", extra_H_link ); output_OEIS_sequence(stdout, 95315,vecA095315, vecA095315[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 2 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095314 in A000040." " Subset: A095287. Subset of A095319." " Cf. also A095335.", NULL ); output_OEIS_sequence(stdout, 95335,vecA095335, expi, 1, "Number of A09515-primes in range ]2^n,2^(n+1)]." "\n%C A095335 Ratios a(n)/A036378(n) converge as: 1, 0.5, 1, 0.4," " 0.571429, 0.615385, 0.826087, 0.511628, 0.573333, 0.49635, 0.623529," " 0.506466, 0.615826, 0.523573, 0.631683, 0.499037, 0.593358, 0.497205," " 0.599068, 0.503126, 0.586414, 0.501376, 0.591451, 0.501741, 0.579964," " 0.501731, 0.579953, 0.500653, 0.574745, 0.501264, 0.574454, 0.501433," " 0.570449" "\n%C A095335 Ratios a(n)/A095296(n) converge as: 1, 1, 1, 0.666667, 0.8," "1.6, 1.1875, 1.047619, 0.895833, 0.985507, 0.908571, 1.026201," "1.015123, 1.098958, 1.034595, 0.996154, 1.016252, 0.98888, 0.99557," "1.012581, 1.008245, 1.005518, 1.011728, 1.006987, 1.006148, 1.006948," "1.00328, 1.002615, 1.002721, 1.00507, 1.004757, 1.005748, 1.003766", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095334(n).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95318,vecA095318, vecA095318[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 3 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095319 in A000040. Subset of A095314. Subset: A095322." " Cf. also A095328.", NULL ); output_OEIS_sequence(stdout, 95328,vecA095328, expi, 1, "Number of A095318-primes in range ]2^n,2^(n+1)]." "\n%C A095328 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0.2, 0.428571," " 0.076923, 0.173913, 0.302326, 0.426667, 0.255474, 0.376471, 0.267241," " 0.384174, 0.289082, 0.368317, 0.300753, 0.406642, 0.312898, 0.400932," " 0.324844, 0.413586, 0.328839, 0.408549, 0.336542, 0.420036, 0.345166," " 0.420047, 0.349607, 0.425255, 0.354353, 0.425546, 0.359213, 0.429551" "\n%C A095328 Ratios a(n)/A095055(n) converge as: 1, 1, 1, 1, 1.5," " 0.333333, 0.571429, 1.181818, 1.185185, 0.875, 1.2, 0.953846," " 0.976676, 0.966805, 0.945763, 0.97779, 0.977197, 0.98472, 1.006694," " 0.995088, 0.988538, 0.987616, 0.983496, 0.990015, 0.991634, 0.994496," " 0.995506, 0.991599, 0.996345, 0.993681, 0.993649, 0.995067, 0.995042", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095329(n).", extra_H_link ); output_OEIS_sequence(stdout, 95319,vecA095319, vecA095319[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 3 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)" "\n%C A095319 Differs from primes (A000040) first time at n=11," " where a(11)=37, while A000040(11)=31, as 31 whose binary" " expansion is 11111, with 5 1-bits and no 0-bits is the first" " prime excluded from this sequence.", "Jun 03 2004", "Complement of A095318 in A000040. Subset of A095323, subset: A095315." " A095329.", NULL ); output_OEIS_sequence(stdout, 95329,vecA095329, expi, 1, "Number of A095319-primes in range ]2^n,2^(n+1)]." "\n%C A095329 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 0.8, 0.571429," " 0.923077, 0.826087, 0.697674, 0.573333, 0.744526, 0.623529, 0.732759," " 0.615826, 0.710918, 0.631683, 0.699247, 0.593358, 0.687102, 0.599068," " 0.675156, 0.586414, 0.671161, 0.591451, 0.663458, 0.579964, 0.654834," " 0.579953, 0.650393, 0.574745, 0.645647, 0.574454, 0.640787, 0.570449" "\n%C A095329 Ratios a(n)/A095020(n) converge as: 1, 1, 1, 1, 0.8, 1.2," "1.1875, 0.9375, 0.895833, 1.051546, 0.908571, 1.017964, 1.015123," "1.014159, 1.034595, 1.009866, 1.016252, 1.007117, 0.99557, 1.002381," "1.008245, 1.006182, 1.011728, 1.005142, 1.006148, 1.002926, 1.00328," "1.004575, 1.002721, 1.003502, 1.004757, 1.002787, 1.003766", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095328(n).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95322,vecA095322, vecA095322[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 4 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095323 in A000040. Subset of A095318. Subset: A095284." " Cf. also A095324.", NULL ); output_OEIS_sequence(stdout, 95324,vecA095324, expi, 1, "Number of A095322-primes in range ]2^n,2^(n+1)]." "\n%C A095324 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0.2, 0," " 0.076923, 0.173913, 0.302326, 0.106667, 0.255474, 0.172549, 0.267241," " 0.172018, 0.289082, 0.231353, 0.300753, 0.216392, 0.312898, 0.242112," " 0.324844, 0.245432, 0.328839, 0.262367, 0.336542, 0.268304, 0.345166," " 0.278603, 0.349607, 0.283298, 0.354353, 0.29269, 0.359213, 0.296876" "\n%C A095324 Ratios a(n)/A095019(n) converge as: 1, 1, 1, 1, 1," " 0.333333, 1.333333, 1.181818, 0.8, 0.875, 0.846154, 0.953846," " 0.974026, 0.966805, 1.080123, 0.97779, 0.93677, 0.98472, 0.970332," " 0.995088, 0.9894, 0.987616, 0.985673, 0.990015, 0.994846, 0.994496," " 0.987642, 0.991599, 0.988865, 0.993681, 0.996653, 0.995067, 0.994296", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095325(n).", extra_H_link ); output_OEIS_sequence(stdout, 95323,vecA095323, vecA095323[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 4 + number of 0-bits." "\n%C A095323 Differs from primes (A000040) first time at n=11," " where a(11)=37, while A000040(11)=31, as 31 whose binary" " expansion is 11111, with 5 1-bits and no 0-bits is the first" " prime excluded from this sequence." " Note that 15 (1111 in binary) is not prime.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095322 in A000040. Subset of A095285. subset: A095319." " A095325.", NULL ); output_OEIS_sequence(stdout, 95325,vecA095325, expi, 1, "Number of A095323-primes in range ]2^n,2^(n+1)]." "\n%C A095325 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 0.8, 1," " 0.923077, 0.826087, 0.697674, 0.893333, 0.744526, 0.827451, 0.732759," " 0.827982, 0.710918, 0.768647, 0.699247, 0.783608, 0.687102, 0.757888," " 0.675156, 0.754568, 0.671161, 0.737633, 0.663458, 0.731696, 0.654834," " 0.721397, 0.650393, 0.716702, 0.645647, 0.70731, 0.640787, 0.703124" "\n%C A095325 Ratios a(n)/A095054(n) converge as: 1, 1, 1, 1, 1, 1.2," " 0.95, 0.9375, 1.030769, 1.051546, 1.039409, 1.017964, 1.005571," "1.014159, 0.97816, 1.009866, 1.018993, 1.007117, 1.009864, 1.002381," "1.003497, 1.006182, 1.005197, 1.005142, 1.001903, 1.002926, 1.004856," "1.004575, 1.004471, 1.003502, 1.001392, 1.002787, 1.002428", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095324(n).", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95284,vecA095284, vecA095284[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 5 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095285 in A000040. Subset of A095322. Subset: A095312." "Cf. also A095286, A095294.", NULL ); output_OEIS_sequence(stdout, 95294,vecA095294, expi, 1, "Number of A095284-primes in range ]2^n,2^(n+1)]." "\n%C A095294 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0, 0," " 0.076923, 0.173913, 0.093023, 0.106667, 0.109489, 0.172549, 0.101293," " 0.172018, 0.146402, 0.231353, 0.151165, 0.216392, 0.161746, 0.242112," " 0.175754, 0.245432, 0.191264, 0.262367, 0.202279, 0.268304, 0.210966," " 0.278603, 0.219599, 0.283298, 0.228618, 0.29269, 0.235729, 0.296876" "\n%C A095294 Ratios a(n)/A095327(n) converge as: 1, 1, 1, 1, 1, 0," "1.333333, 4., 0.8, 1, 0.846154, 0.903846, 0.974026, 1.18593, 1.080123," "1.015294, 0.93677, 0.960116, 0.970332, 0.987101, 0.9894, 0.998326," " 0.985673, 0.997384, 0.994846, 0.988856, 0.987642, 0.987035, 0.988865," " 0.993762, 0.996653, 0.994302, 0.994296", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095295(n). Cf. also A095329, A095052, A095053", extra_H_link ); output_OEIS_sequence(stdout, 95285,vecA095285, vecA095285[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 5 + number of 0-bits." "\n%C A095285 Differs from primes (A000040) first time at n=31," " where a(31)=131, while A000040(31)=127, as 127 whose binary" " expansion is 1111111, with 7 1-bits and no 0-bits is the first" " prime excluded from this sequence. Note that 63 (111111 in binary)" " is not prime.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095284 in A000040. Subset: A095323." " Subset of A095313, from which it differs first time at n=42," " where a(42)=193 (11000001 in binary) while" " A095313(42)=191 (10111111 in binary)." " Cf. also A095286, A095295.", NULL ); output_OEIS_sequence(stdout, 95295,vecA095295, expi, 1, "Number of A095285-primes in range ]2^n,2^(n+1)]." "\n%C A095295 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 1, 1," " 0.923077, 0.826087, 0.906977, 0.893333, 0.890511, 0.827451, 0.898707," " 0.827982, 0.853598, 0.768647, 0.848835, 0.783608, 0.838254, 0.757888," " 0.824246, 0.754568, 0.808736, 0.737633, 0.797721, 0.731696, 0.789034," " 0.721397, 0.780401, 0.716702, 0.771382, 0.70731, 0.764271, 0.703124" "\n%C A095295 Ratios a(n)/A095326(n) converge as: 1, 1, 1, 1, 1," " 0.923077, 0.95, 0.928571, 1.030769, 1, 1.039409, 1.012136, 1.005571," " 0.973815, 0.97816, 0.997325, 1.018993, 1.00808, 1.009864, 1.002794," "1.003497, 1.000397, 1.005197, 1.000665, 1.001903, 1.003022, 1.004856," "1.00371, 1.004471, 1.001864, 1.001392, 1.001771, 1.002428", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", /* "a(n) = A095286(n) + (if n is something cf. A095052,A095053" */ "a(n) = A036378(n)-A095294(n). A095052, A095053", extra_H_link ); /******************************/ output_OEIS_sequence(stdout, 95312,vecA095312, vecA095312[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is > 6 + number of 0-bits.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095313 in A000040. Subset of A095284." " Cf. also A095332.", NULL ); output_OEIS_sequence(stdout, 95332,vecA095332, expi, 1, "Number of A095312-primes in range ]2^n,2^(n+1)]." "\n%C A095332 Ratios a(n)/A036378(n) converge as: 0, 0, 0, 0, 0," " 0.076923, 0, 0.093023, 0.04, 0.109489, 0.035294, 0.101293, 0.083716," " 0.146402, 0.082838, 0.151165, 0.109778, 0.161746, 0.110884, 0.175754," " 0.132525, 0.191264, 0.142826, 0.202279, 0.154244, 0.210966, 0.161036," " 0.219599, 0.172971, 0.228618, 0.179496, 0.235729, 0.188283" "\n%C A095332 Ratios a(n)/A095331(n) converge as: 1, 1, 1, 1, 1, 0, 1," "4, 0.75, 1, 0.642857, 0.903846, 0.879518, 1.18593, 0.965385," "1.015294, 0.980066, 0.960116, 0.932115, 0.987101, 0.973972, 0.998326," "1.012223, 0.997384, 0.985958, 0.988856, 0.981798, 0.987035, 0.991666," " 0.993762, 0.991831, 0.994302, 0.992846", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095333(n).", extra_H_link ); output_OEIS_sequence(stdout, 95313,vecA095313, vecA095313[0], /* Contains the count of collected primes. */ 1, "Primes in whose binary expansion" " the number of 1-bits is <= 6 + number of 0-bits." "\n%C A095313 Differs from primes (A000040) first time at n=31," " where a(31)=131, while A000040(31)=127, as 127 whose binary" " expansion is 1111111, with 7 1-bits and no 0-bits is the first" " prime excluded from this sequence.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Complement of A095312 in A000040." " Subset: A095285, from which it differs first time at n=42," " where a(42)=191 (10111111 in binary), while A095285(42)=193" " (11000001 in binary)." "Cf. also A095333.", NULL ); output_OEIS_sequence(stdout, 95333,vecA095333, expi, 1, "Number of A095313-primes in range ]2^n,2^(n+1)]." "\n%C A095333 Ratios a(n)/A036378(n) converge as: 1, 1, 1, 1, 1," " 0.923077, 1, 0.906977, 0.96, 0.890511, 0.964706, 0.898707, 0.916284," " 0.853598, 0.917162, 0.848835, 0.890222, 0.838254, 0.889116, 0.824246," " 0.867475, 0.808736, 0.857174, 0.797721, 0.845756, 0.789034, 0.838964," " 0.780401, 0.827029, 0.771382, 0.820504, 0.764271, 0.811717" "\n%C A095333 Ratios a(n)/A095330(n) converge as: 1, 1, 1, 1, 1," " 0.923077, 1, 0.928571, 1.014085, 1, 1.020747, 1.012136, 1.012674," " 0.973815, 1.003249, 0.997325, 1.002514, 1.00808, 1.009166, 1.002794," "1.004099, 1.000397, 0.997992, 1.000665, 1.002604, 1.003022, 1.003571," "1.00371, 1.001761, 1.001864, 1.001805, 1.001771, 1.001674", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "a(n) = A036378(n)-A095332(n).", extra_H_link ); /******************************/ /* Compute also for higher bases, and similar seq. for A014580. For all odd numbers as well, but for that we should have a simple formula. */ output_OEIS_sequence(stdout, 95298,vecA095298, expi, 1, "Sum of 1-bits between the most and least significant bits" " summed for all primes in range ]2^n,2^(n+1)]." "\n%e A095298 a(1)=0, as only prime in range ]2,4] is 3, which has " " no space between its most and least significant digits." " a(2)=1, as in that range there are two primes 5 (101 in binary)" " and 7 (111 in binary) and summing their middle bits we get 1." " a(3)=2, as there are again two primes, 11 (1011 in binary), and" " 13 (1101 in binary), and summing the bits in the middle we get total 2.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Cf. A095297, A095334, A095353.", NULL ); output_OEIS_sequence(stdout, 95336,vecA095336, expi, 1, "Sum of 1-fibits in Zeckendorf-expansion A014417(p) summed for all" " primes p in range ]2^n,2^(n+1)]." "\n%e A095336 a(1)=1, as only prime in range ]2,4] is 3, whose " "Fibonacci-representation is 100. In the next range we have primes 5 and 7," " whose Fibonacci-representations are 1000 and 1010 respectively, thus " " a(2)=3.", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Cf. A095298, A095353.", NULL ); /* Last term shown is not necessarily incorrect, if we have computed more terms than output_OEIS_sequence has printed. */ output_OEIS_sequence(stdout, 95353,vecA095353, binwidth(A003714(stop)), 1, "Sum of 1-fibits in Zeckendorf-expansion A014417(p) summed for all" " primes p in range [Fib(n+1),Fib(n+2)[ (where Fib = A000045)." "\n%e A095353 a(1) = a(2) = 0, as there are no primes in ranges" " [1,2[ and [2,3[. a(3)=1 as in [3,5[ there is prime 3" " with Fibonacci-representation 100. a(4)=3, as in [5,8[ there are" " primes 5 and 7, whose Fibonacci-representations are 1000 and 1010" " respectively, and we have three 1-fibits in total." " a(5)=2, as in [8,13[ there is only one prime 11, with " " Zeckendorf-representation 10100." "\n** DISCARD THE LAST NON-ZERO ENTRY BEFORE SUBMITTING, IT'S INCORRECT **", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Cf. A095336.", NULL ); output_OEIS_sequence(stdout, 95354,vecA095354, binwidth(A003714(stop)), 1, "Number of primes p such that Fib(n+1) <= p < Fib(n+2)," " (where Fib = A000045)." "\n%e A095354 I.e. gives the number of primes whose Zeckendorf-expansion" " is n fibits long. a(1) = a(2) = 0, as there are no primes in ranges" " [1,2[ and [2,3[. a(3)=1 as in [3,5[ there is prime 3" " with Fibonacci-representation 100. a(4)=2, as in [5,8[ there are" " primes 5 and 7. a(5)=1, as in [8,13[ there is only one prime 11," " and a(6)=3 as in [13,21[ there are primes 13,17,19." "\n** DISCARD THE LAST NON-ZERO ENTRY BEFORE SUBMITTING, IT'S INCORRECT **", "Antti Karttunen (his-firstname.his-surname(AT)iki.fi)", "Jun 03 2004", "Cf. A095353, A036378.", NULL ); /******************************/ } /* This part could be more systematic. Still, what we could do: - similarly, divide A027697 into A091206\{3} and odious members of A091209. - Cryptographically strong primes (whatever that currently means...) */ #define add_p_to_vector(p,vec)\ if((vec)[0] < max_terms_collected)\ {\ (vec)[(int)(++(vec)[0])] = (p);\ } prime_found(ULLI p,int max_terms_collected) { int sz = binwidth(p); int w = sz - 1; int one_bits = A000120(p); int zero_bits = sz - one_bits; int twice_one_bits = (one_bits << 1); int is_odious = (one_bits & 1); /* Was = A010060(p); */ int mod6; int ind; static int prev_w = 0; static ULLI prev_prime = 0; if(w != prev_w) { fprintf(stderr,"w=%u\n",w); /* To spirit our patience. */ fflush(stderr); prev_w = w; } if(0) { fprint_ulli(stdout,p); fprintf(stdout," %d %d %d\n",w,is_odious,twice_one_bits); } vecA036378[w]++; vecA095298[w] += (one_bits-2); /* MSB and LSB are 1 in any case.*/ /*** Odious prime (A027697) or Evil prime (A027699): ***/ if(is_odious) { vecA095005[w]++; add_p_to_vector(p,vecA027697); } else { vecA095006[w]++; add_p_to_vector(p,vecA027699); } if(1 & A007814(p+1)) /* Number of trailing ones is odd? (in A079523) */ { vecA095293[w]++; add_p_to_vector(p,vecA095283); } else /* No, it's even (in complement of A079523). */ { vecA095292[w]++; add_p_to_vector(p,vecA095282); } /*** Other measures involving number of 0- and 1-bits. ***/ if(twice_one_bits == (sz-1)) /* One more 0- than 1-bits. */ { vecA095052[w]++; add_p_to_vector(p,vecA095072); } else if(twice_one_bits == (sz+1)) /* One more 1- than 0-bits. */ { vecA095053[w]++; add_p_to_vector(p,vecA095073); } /**********************************/ if(one_bits > (zero_bits-3)) { add_p_to_vector(p,vecA095320); vecA095330[w]++; } else /* if(ones_bits <= (zero_bits-3)) */ { add_p_to_vector(p,vecA095321); vecA095331[w]++; } if(one_bits > (zero_bits-2)) { add_p_to_vector(p,vecA095316); vecA095326[w]++; } else /* if(ones_bits <= (zero_bits-2)) */ { add_p_to_vector(p,vecA095317); vecA095327[w]++; } if(one_bits > (zero_bits-1)) /* Not zero-bit-dominant. */ { vecA095054[w]++; add_p_to_vector(p,vecA095074); } else /* if(ones_bits <= (zero_bits-1)) */ /* Zero-bit dominant? */ { add_p_to_vector(p,vecA095071); vecA095019[w]++; } /* If number of 1-bits is exactly half of the binary width, then we have a binarily balanced prime: */ if(one_bits == zero_bits) { vecA095018[w]++; } if(one_bits > zero_bits) /* One-bit dominant. */ { add_p_to_vector(p,vecA095070); vecA095020[w]++; } else /* if(one_bits <= zero_bits) */ /* Not one-bit-dominant. */ { add_p_to_vector(p,vecA095075); vecA095055[w]++; } if(one_bits > (1+zero_bits)) { add_p_to_vector(p,vecA095286); vecA095296[w]++; } else /* if(one_bits <= (1+zero_bits)) */ { add_p_to_vector(p,vecA095287); vecA095297[w]++; } if(one_bits > (2+zero_bits)) { add_p_to_vector(p,vecA095314); vecA095334[w]++; } else /* if(one_bits <= (2+zero_bits)) */ { add_p_to_vector(p,vecA095315); vecA095335[w]++; } if(one_bits > (3+zero_bits)) { add_p_to_vector(p,vecA095318); vecA095328[w]++; } else /* if(one_bits <= (3+zero_bits)) */ { add_p_to_vector(p,vecA095319); vecA095329[w]++; } if(one_bits > (4+zero_bits)) { add_p_to_vector(p,vecA095322); vecA095324[w]++; } else /* if(one_bits <= (4+zero_bits)) */ { add_p_to_vector(p,vecA095323); vecA095325[w]++; } if(one_bits > (5+zero_bits)) { add_p_to_vector(p,vecA095284); vecA095294[w]++; } else /* if(one_bits <= (5+zero_bits)) */ { add_p_to_vector(p,vecA095285); vecA095295[w]++; } if(one_bits > (6+zero_bits)) { add_p_to_vector(p,vecA095312); vecA095332[w]++; } else /* if(one_bits <= (6+zero_bits)) */ { add_p_to_vector(p,vecA095313); vecA095333[w]++; } /**********************************/ if(3 == one_bits) { vecA095056[w]++; } if(4 == one_bits) { vecA095057[w]++; add_p_to_vector(p,vecA095077); } if(1 == (sz - one_bits)) { vecA095058[w]++; add_p_to_vector(p,vecA095078); } if(2 == (sz - one_bits)) { vecA095059[w]++; add_p_to_vector(p,vecA095079); } /*** Modulo 4. ***/ if(1 == (p & 3)) { vecA095007[w]++; } /* Primes of the form 4k+1. */ else { vecA095008[w]++; } /* Primes of the form 4k+3. */ /*** Modulo 8. ***/ switch(p & 7) /* I.e. modulo 8. */ { case 1: { vecA095009[w]++; /* Primes of the form 8k+1. */ vecA095013[w]++; /* Primes of the form 8k+-1. */ break; } case 3: { vecA095010[w]++; /* Primes of the form 8k+3. */ vecA095014[w]++; /* Primes of the form 8k+-3. */ break; } case 5: { vecA095011[w]++; /* Primes of the form 8k+5. */ vecA095014[w]++; /* Primes of the form 8k+-3. */ break; } case 7: { vecA095012[w]++; /* Primes of the form 8k+5. */ vecA095013[w]++; /* Primes of the form 8k+-1. */ break; } default: { fprintf(stderr,"Prime "); fprint_ulli(stderr,p); fprintf(stderr, " with weight %d and odiousness %d,", w,is_odious); fprintf(stderr," has impossible congruence modulo 8: %d\n", ((int)(p & 7))); exit(1); } } /*** Modulo 6. ***/ mod6 = (p % 6); if(1 == mod6) { vecA095015[w]++; } /* Primes of the form 6k+1. */ else if(5 == mod6) { vecA095016[w]++; } /* Primes of the form 6k+5. */ /*** Modulo 5. ***/ switch(p % 5) { case 0: { break; } /* Five itself. Ignore. */ case 1: { vecA095021[w]++; break; } case 2: { vecA095022[w]++; break; } case 3: { vecA095023[w]++; break; } case 4: { vecA095024[w]++; break; } } /*** Zeckendorf-expansion (Fibonacci-number system). ***/ if(1) /* Check the Zeckendorf-expansion as well. */ { ULLI ze = A003714(p); int num_of_fibits = binwidth(ze); int num_of_1_fibits = A000120(ze); int is_fibodious = (num_of_1_fibits & 1); /* Was = A010060(ze); */ int is_upper_Wythoff_prime = (A007814(ze) & 1); /* ze. ends with odd number of 0s. */ vecA095336[w] += num_of_1_fibits; vecA095353[num_of_fibits] += num_of_1_fibits; vecA095354[num_of_fibits]++; /* Primes in this F-range. */ if(is_fibodious) { vecA095063[w]++; add_p_to_vector(p,vecA095083); } else /* No, it's fibevil. */ { vecA095064[w]++; add_p_to_vector(p,vecA095084); } if(is_upper_Wythoff_prime) /* It's in A001950. */ { vecA095291[w]++; add_p_to_vector(p,vecA095281); } else /* No, lower Wythoff prime (in A000201). */ { vecA095290[w]++; add_p_to_vector(p,vecA095280); } switch(ze & 7) /* We are interested about the three rightmost fibits. */ { case 0: /* 000 */ { vecA095065[w]++; add_p_to_vector(p,vecA095085); vecA095062[w]++; add_p_to_vector(p,vecA095082); /* 00 */ vecA095060[w]++; add_p_to_vector(p,vecA095080); /* 0 */ break; } case 1: /* 001 */ { vecA095066[w]++; add_p_to_vector(p,vecA095086); vecA095061[w]++; add_p_to_vector(p,vecA095081); /* 1 */ break; } case 2: /* 010 */ { vecA095067[w]++; add_p_to_vector(p,vecA095087); vecA095060[w]++; add_p_to_vector(p,vecA095080); /* 0 */ break; } case 4: /* 100 */ { vecA095068[w]++; add_p_to_vector(p,vecA095088); vecA095062[w]++; add_p_to_vector(p,vecA095082); /* 00 */ vecA095060[w]++; add_p_to_vector(p,vecA095080); /* 0 */ break; } case 5: /* 101 */ { vecA095069[w]++; add_p_to_vector(p,vecA095089); vecA095061[w]++; add_p_to_vector(p,vecA095081); /* 1 */ break; } default: { fprintf(stderr,"Prime "); fprint_ulli(stderr,p); fprintf(stderr, " with weight %d and odiousness %d,", w,is_odious); fprintf(stderr," has impossible Zeckendorf-expansion: "); fprint_ulli(stderr,ze); fprintf(stderr," as modulo 8 it results %u.\n", ((int)(ze&7))); exit(1); } } } /*** Is the Legendre-vector a valid Dyck-path? (Much heavier test) ***/ if(w <= glob_dyckness_checked_only_up_to_n) { int di = js_diving_index(p,(p-1)/2); if(3 == (p & 3)) /* Primes of the form 4k+3. */ { int max_dyck_prefix = ((0 == di) ? (p-1) : (di-1)); add_p_to_vector(di,vecA095104); add_p_to_vector(max_dyck_prefix,vecA095105); vecA095106[w] += di; vecA095107[w] += max_dyck_prefix; if(0 == di) /* Is a valid Dyck path. */ { vecA095092[w]++; add_p_to_vector(p,vecA095102); add_p_to_vector((p-3)>>2,vecA095272); /* Corresponding k values. */ } else { vecA095093[w]++; add_p_to_vector(p,vecA095103); add_p_to_vector(di,vecA095108); add_p_to_vector((p-3)>>2,vecA095273); /* Corresponding k values. */ } } if(0 == di) /* The first half is a valid Dyck path? */ { vecA095094[w]++; add_p_to_vector(p,vecA080114); } else { vecA095095[w]++; add_p_to_vector(p,vecA080115); } } /*** Twin Primes. ***/ if((prev_prime + 2) == p) /* Found a pair of primes. (twin primes). */ { int w2 = binwidth(prev_prime)-1; vecA095017[w2]++; /* Lesser twin primes (subset of 6k+5 primes). */ } prev_prime = p; } /* A095100 is for all odd numbers of form 4k+3 whose jacobi-vector = valid Motzkin path. and A095101 is for its complement (among 4k+3 integers). (compute also sum of their diving indices, and its average for each ]2^n,2^(n+1)] range. Moments, etc.) A095090 and A095091 are for the respective counts. */ iterate_over_4k_plus3(int upto_w,int max_terms_collected) { int w,n,next_lim; /* w=1, n=3; w=2, n=7; w=3, n=11,15; w=4, n=19,21,25,29; */ for(w=1, n=3; w <= upto_w; w++) { fprintf(stderr,"iterate_over_4k_plus3: w=%u\n",w); fflush(stderr); for(next_lim = power_of_2(w+1); n < next_lim; n += 4) { int di = js_diving_index(n,(n-1)/2); int max_dyck_prefix = ((0 == di) ? (n-1) : (di-1)); add_p_to_vector(di,vecA095269); add_p_to_vector(max_dyck_prefix,vecA095270); vecA095109[w] += di; vecA095110[w] += max_dyck_prefix; if(0 == di) /* It is a valid Motzkin path. */ { vecA095090[w]++; add_p_to_vector(n,vecA095100); add_p_to_vector((n-3)>>2,vecA095274); /* Corresponding k values. */ } else { vecA095091[w]++; add_p_to_vector(n,vecA095101); add_p_to_vector(di,vecA095271); add_p_to_vector((n-3)>>2,vecA095275); /* Corresponding k values. */ } } } } /**********************************************************************/ /* */ /* */ /* This part by John Moyer (jrm(AT)rsok.com, */ /* Copyright 1999-2004 (C) John Moyer. */ /* */ /* This is actually borrowed from his 64bit sieve program */ /* (11.December 2002 version), */ /* which is available at */ /* ftp://ftp.rsok.com/pub/source/sieve2310_64bit.c */ /* See also: http://www.rsok.com/~jrm/ */ /* */ /* */ /**********************************************************************/ #define STEP_CONST 128 int small_primes[343] = { 2,3,5,7,11,13,17,19,23,29, 31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113, 127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211,223,227,229, 233,239,241,251,257,263,269,271,277,281, 283,293,307,311,313,317,331,337,347,349, 353,359,367,373,379,383,389,397,401,409, 419,421,431,433,439,443,449,457,461,463, 467,479,487,491,499,503,509,521,523,541, 547,557,563,569,571,577,587,593,599,601, 607,613,617,619,631,641,643,647,653,659, 661,673,677,683,691,701,709,719,727,733, 739,743,751,757,761,769,773,787,797,809, 811,821,823,827,829,839,853,857,859,863, 877,881,883,887,907,911,919,929,937,941, 947,953,967,971,977,983,991,997,1009,1013, 1019,1021,1031,1033,1039,1049,1051,1061,1063,1069, 1087,1091,1093,1097,1103,1109,1117,1123,1129,1151, 1153,1163,1171,1181,1187,1193,1201,1213,1217,1223, 1229,1231,1237,1249,1259,1277,1279,1283,1289,1291, 1297,1301,1303,1307,1319,1321,1327,1361,1367,1373, 1381,1399,1409,1423,1427,1429,1433,1439,1447,1451, 1453,1459,1471,1481,1483,1487,1489,1493,1499,1511, 1523,1531,1543,1549,1553,1559,1567,1571,1579,1583, 1597,1601,1607,1609,1613,1619,1621,1627,1637,1657, 1663,1667,1669,1693,1697,1699,1709,1721,1723,1733, 1741,1747,1753,1759,1777,1783,1787,1789,1801,1811, 1823,1831,1847,1861,1867,1871,1873,1877,1879,1889, 1901,1907,1913,1931,1933,1949,1951,1973,1979,1987, 1993,1997,1999,2003,2011,2017,2027,2029,2039,2053, 2063,2069,2081,2083,2087,2089,2099,2111,2113,2129, 2131,2137,2141,2143,2153,2161,2179,2203,2207,2213, 2221,2237,2239,2243,2251,2267,2269,2273,2281,2287, 2293,2297,2309 }; /* expand scheme from 30 to 2310 30 == 2*3*5 and 8 == (2-1)*(3-1)*(5-1) 2*3*5*7*11 == 2310 1*2*4*6*10 == 480 bits == 60 bytes ==> prime or not prime for 38.5 integers per byte In each 2310 integers, for N >= 1, the numbers that might be prime are: N*2310+1, N*2310+13, N*2310+17, . . . N*2310+13*13, N*2310+13*17, . . . N*2310+2309 */ unsigned long maskbits[32] = { 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000 }; /* value of mask_bit_index is bit corresponding to integer modulo 2310 mask_bit_index[i] is zero if this is integer that could not possibly be prime or bit number from 1 to 480 if it could be prime. */ unsigned int mask_bit_index[2310]; /* bit is one to 480 */ void clear_one_mask_bit(unsigned long *sieve_array, int bit) { int k; k = (bit - 1) >> 5 ; /* divide by 32 */ sieve_array[k] &= ~(maskbits[(bit - 1) & 31]); /* modulo 32 */ #ifdef DEBUG printf("sieve_array[%d]=0x%08x, ~(maskbits[(%d - 1) & 31]=0x%08x\n", k, sieve_array[k], bit, ~(maskbits[(bit - 1) & 31])); #endif } /* bit is one to 480 */ int test_one_mask_bit(unsigned long *sieve_array, int bit) { int k; k = (bit - 1) >> 5 ; /* divide by 32 */ return (sieve_array[k] & (maskbits[(bit - 1) & 31])); /* modulo 32 */ } int compute_primes(ULLI start, ULLI stop,int max_terms_collected) { unsigned int b; unsigned long s; ULLI k, j, ii; ULLI i; unsigned int bit_index = 0; ULLI indx; int c; unsigned long *list; FILE *fp; ULLI stop_here, t_stop_here; char ifnam[2048]; int errflag = 0; int write_flag = 0; s = (stop+2309)/2310 * 60 +60; /* bytes required */ fprintf(stderr,"Computing from "); fprint_ulli(stderr,start); fprintf(stderr," to "); fprint_ulli(stderr,stop); fprintf(stderr,", "); fprint_ulli(stderr,((ULLI)s)); fprintf(stderr," bytes required.\n\n\n"); /* print the first few small primes if they were requested */ for ( i = 0 ; i < 344 ; i ++) { if ( small_primes[i] > stop ) return 0; /* return to OS if nothing more to do */ if ( small_primes[i] >= start ) { prime_found(small_primes[i],max_terms_collected); } } fprintf(stderr,"attempting to malloc %lu bytes\n", s); list = malloc(s); if ( list == NULL ) { fprintf(stderr, "Could not allocate %lu bytes of memory\n", s); exit(1); } memset(list,0xff,s); j = 5; /* create array mapping 2310 integers to 480 bits */ mask_bit_index[0] = bit_index++; mask_bit_index[1] = bit_index++; for ( ii = 2; ii < 2310 ; ii++ ) { while (small_primes[j] < ii ) j++; /* if modulo any of the prime factors of 2310, then could not be prime */ if ( ii == small_primes[j] || ((ii%2)!=0 && (ii%3)!=0 && (ii%5)!=0 && (ii%7)!=0 && (ii%11)!=0)) { mask_bit_index[ii] = bit_index++; } else mask_bit_index[ii] = 0; #ifdef DEBUG printf("mask_bit_index[%d]=%u, j=%d\n", ii, mask_bit_index[ii], j); #endif } indx = 0L; stop_here = (unsigned long) (sqrt((stop+2309.0)/2310.0 *2310.0) + 0.5); for ( k = 0 ; k*2310 < stop ; k+=STEP_CONST ) { /* no need to sieve numbers larger than this range */ t_stop_here = (k+STEP_CONST)*2310UL; if ( stop_here < t_stop_here ) t_stop_here = stop_here; for( i = 13 ; i <= t_stop_here ; i+=2 ) { /* start with 13 since multiples of 2,3,5,7,11 are handled by the storage method */ /* increment by 2 for odd numbers only */ /* if ( (i >= ((k+STEP_CONST)* 2310))) break; /* no need to sieve numbers larger than this range, do next k */ b = i % 2310; /* i could not possibly be prime if remainder is 2,3,4,7,11 */ if ( mask_bit_index[b] == 0 || (i < k*2310 && (test_one_mask_bit(&list[i/2310 *15], mask_bit_index[b]))==0 ) ) continue; /* or this one already marked so it is not a prime */ /* */ if ( k == 0 ) indx = i*i; else indx = (k*2310) - (k*2310)%i +i; if ( (indx & 1) == 0 ) indx += i; /* start with i*i since any integer < i has already been sieved */ /* add 2 * i to avoid even numbers and mark all multiples of this prime */ for ( ; indx < (k+STEP_CONST)*2310 && indx <= (stop+2309)/2310*2310 ; indx +=(i+i)) { b = indx % 2310; /* modulo 2310 */ if ( mask_bit_index[b] != 0 ) { clear_one_mask_bit(&list[indx/2310 *15],mask_bit_index[b]); #ifdef DEBUG printf("indx = %lu, mask_bit_index[%d]=%d\n", indx, b, mask_bit_index[b]); #endif } } /* for indx */ } /* for i */ if ( start < (k+STEP_CONST)*2310 ) /* are there some to print now? */ { if ( k*2310 < start ) i = start; else i = k*2310; if ( (i & 1) == 0 ) i++; /* force it to be odd */ if ( 2311 >= i ) i = 2311; for ( ; i <= stop && i < (k+STEP_CONST)*2310; i+=2 ) { b = i % 2310; if ( mask_bit_index[b] != 0 && i >= start && (test_one_mask_bit(&list[i/2310 *15], mask_bit_index[b]))!=0 ) { prime_found(i,max_terms_collected); } } /* for i */ } } /* for k */ if(write_flag) { if(NULL == (fp = fopen(ifnam,"wb"))) { perror(ifnam); return 1; } i = fwrite( list, 1L, s, fp ); if(i != s) { fprintf(stderr,"write error: i=%Lu, s=%lu\n",i,s); } } return 0; }