%I #27 Mar 01 2022 05:32:01
%S 1,0,1,2,1,2,3,4,6,10,16,26,45,78,138,244,439,784,1417,2572,4698,8682,
%T 16021,29720,55146,102170,190274,356804,671224,1269022,2404289,
%U 4521836,8535117,16134474,30635869,58062404,110496946,210500898,401422210,767158570,1467402238
%N Number of solutions to +-2 +- 3 +- 5 +- 7 +- ... +- prime(n) = 0 or 1.
%H Alois P. Heinz, <a href="/A350404/b350404.txt">Table of n, a(n) for n = 0..2000</a>
%e a(6) = 3: 2 + 3 + 5 - 7 + 11 - 13 =
%e -2 + 3 + 5 - 7 - 11 + 13 =
%e -2 + 3 - 5 + 7 + 11 - 13 = 1.
%p s:= proc(n) s(n):= `if`(n<1, 0, ithprime(n)+s(n-1)) end:
%p b:= proc(n, i) option remember; `if`(n>s(i), 0, `if`(i=0, 1,
%p b(n+ithprime(i), i-1)+b(abs(n-ithprime(i)), i-1)))
%p end:
%p a:=n-> b(0, n)+b(1, n):
%p seq(a(n), n=0..45); # _Alois P. Heinz_, Jan 16 2022
%t s[n_] := s[n] = If[n < 1, 0, Prime[n] + s[n - 1]];
%t b[n_, i_] := b[n, i] = If[n > s[i], 0, If[i == 0, 1,
%t b[n + Prime[i], i - 1] + b[Abs[n - Prime[i]], i - 1]]];
%t a[n_] := b[0, n] + b[1, n];
%t Table[a[n], {n, 0, 45}] (* _Jean-François Alcover_, Mar 01 2022, after _Alois P. Heinz_ *)
%o (Python)
%o from itertools import product
%o from sympy import prime, primerange
%o def a(n):
%o if n == 0: return 1
%o nn = ["0"] + [str(i) for i in primerange(2, prime(n)+1)]
%o return sum(eval("".join([*sum(zip(nn, ops+("", )), ())])) in {0, 1} for ops in product("+-", repeat=n))
%o print([a(n) for n in range(18)]) # _Michael S. Branicky_, Jan 16 2022
%o (Python)
%o from sympy import sieve, primerange
%o from functools import cache
%o @cache
%o def b(n, i):
%o maxsum = 0 if i == 0 else sum(p for p in primerange(2, sieve[i]+1))
%o if n > maxsum: return 0
%o if i == 0: return 1
%o return b(n+sieve[i], i-1) + b(abs(n-sieve[i]), i-1)
%o def a(n): return b(0, n) + b(1, n)
%o print([a(n) for n in range(43)]) # _Michael S. Branicky_, Jan 16 2022
%Y Cf. A000040, A022894, A025591, A113040.
%K nonn
%O 0,4
%A _Ilya Gutkovskiy_, Dec 29 2021
%E a(39)-a(40) from _Michael S. Branicky_, Jan 16 2022
|