login
A109925
Number of primes of the form n - 2^k.
15
0, 0, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 0, 1, 2, 3, 1, 4, 0, 2, 1, 2, 0, 3, 0, 1, 1, 2, 1, 3, 1, 3, 0, 2, 1, 4, 0, 1, 1, 2, 1, 5, 0, 2, 1, 3, 0, 3, 0, 1, 1, 3, 0, 2, 0, 1, 1, 3, 1, 4, 0, 1, 1, 2, 1, 5, 0, 2, 1, 2, 1, 6, 0, 3, 0, 2, 1, 3, 0, 3, 1, 2, 0, 4, 0, 1, 1, 3, 0, 3, 0, 2, 0, 1, 1, 3, 0, 2, 1, 2, 1, 6
OFFSET
1,4
COMMENTS
Erdős conjectures that the numbers in A039669 are the only n for which n-2^r is prime for all 2^r<n. - T. D. Noe and Robert G. Wilson v, Jul 19 2005
a(A006285(n)) = 0. - Reinhard Zumkeller, May 27 2015
FORMULA
a(A118954(n))=0, a(A118955(n))>0; A118952(n)<=a(n); A078687(n)=a(A000040(n)). - Reinhard Zumkeller, May 07 2006
G.f.: ( Sum_{i>=0} x^(2^i) ) * ( Sum_{j>=1} x^prime(j) ). - Ilya Gutkovskiy, Feb 10 2022
EXAMPLE
a(21) = 4, 21-2 =19, 21-4 = 17, 21-8 = 13, 21-16 = 5, four primes.
127 is the smallest odd number > 1 such that a(n) = 0: A006285(2) = 127. - Reinhard Zumkeller, May 27 2015
MAPLE
A109925 := proc(n)
a := 0 ;
for k from 0 do
if n-2^k < 2 then
return a ;
elif isprime(n-2^k) then
a := a+1 ;
end if;
end do:
end proc:
seq(A109925(n), n=1..80) ; # R. J. Mathar, Mar 07 2022
MATHEMATICA
Table[cnt=0; r=1; While[r<n, If[PrimeQ[n-r], cnt++ ]; r=2r]; cnt, {n, 150}] (Noe)
f[n_] := Count[ PrimeQ[n - 2^Range[0, Floor[ Log[2, n]]]], True]; Table[ f[n], {n, 105}] (* Robert G. Wilson v, Jul 21 2005 *)
Table[Count[n - 2^Range[0, Floor[Log2[n]]], _?PrimeQ], {n, 110}] (* Harvey P. Dale, Oct 21 2024 *)
PROG
(Magma) a109925:=function(n); count:=0; e:=1; while e le n do if IsPrime(n-e) then count+:=1; end if; e*:=2; end while; return count; end function; [ a109925(n): n in [1..105] ]; // Klaus Brockhaus, Oct 30 2010
(PARI) a(n)=sum(k=0, log(n)\log(2), isprime(n-2^k)) \\ Charles R Greathouse IV, Feb 19 2013
(Haskell)
a109925 n = sum $ map (a010051' . (n -)) $ takeWhile (< n) a000079_list
-- Reinhard Zumkeller, May 27 2015
(Python)
from sympy import isprime
def A109925(n): return sum(1 for i in range(n.bit_length()) if isprime(n-(1<<i))) # Chai Wah Wu, Nov 29 2023
KEYWORD
easy,nonn
AUTHOR
Amarnath Murthy, Jul 17 2005
EXTENSIONS
Corrected and extended by T. D. Noe and Robert G. Wilson v, Jul 19 2005
STATUS
approved