A317240 - OEIS

%I #25 Jul 14 2021 14:54:07

%S 1,0,1,1,0,1,1,1,1,1,0,1,2,1,1,1,1,1,2,1,2,2,0,1,2,0,2,1,2,1,3,1,1,1,

%T 1,1,2,1,2,3,2,1,4,1,3,2,0,1,2,1,3,2,1,1,3,0,2,3,2,1,3,1,3,3,1,2,4,1,

%U 2,1,3,1,2,1,2,3,2,1,3,1,4,2,2,1,3,1,4,3,2,1,5,3,3,4,0,2,2,1,3,2,2,1,5,1,3

%N Number of representations of n of the form 1 + p1 * (1 + p2* ... * (1 + p_j)...), where [p1, ..., p_j] is a (possibly empty) list of (not necessarily distinct) primes.

%H Alois P. Heinz, <a href="/A317240/b317240.txt">Table of n, a(n) for n = 1..65536</a>

%F a(n) = Sum_{prime p|(n-1)} a((n-1)/p) for n>1, a(1) = 1.

%F a(n) = 0 <=> n in { A180337 }.

%F a(n) >= A317241(n).

%F G.f. A(x) satisfies: A(x) = x * (1 + A(x^2) + A(x^3) + A(x^5) + ... + A(x^prime(k)) + ...). - _Ilya Gutkovskiy_, May 09 2019

%e a(13) = 2: 1 + 2 * (1 + 5) = 1 + 3 * (1 + 3) = 13.

%e a(31) = 3: 1 + 2 * (1 + 2 * (1 + 2 * (1 + 2))) = 1 + 3 * (1 + 3 * (1 + 2)) = 1 + 5 * (1 + 5) = 31.

%p a:= proc(n) option remember; `if`(n=1, 1,

%p       add(a((n-1)/p), p=numtheory[factorset](n-1)))

%p     end:

%p seq(a(n), n=1..200);

%t pp[n_] := pp[n] = FactorInteger[n][[All, 1]];

%t q[n_] := q[n] = Switch[n, 1, True, 2, False, _, AnyTrue[pp[n-1], q[(n-1)/#]&]];

%t a[n_] := a[n] = Which[n == 1, 1, !q[n], 0, True, Sum[a[(n-1)/p], {p, pp[n-1]}]];

%t Array[a, 105] (* _Jean-François Alcover_, Jul 14 2021, after _Alois P. Heinz_ *)

%Y Cf. A180337, A317241, A317384.

%K nonn

%O 1,13

%A _Alois P. Heinz_, Jul 24 2018