A317240 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.

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, 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, 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

Offset

1,13

Links

Alois P. Heinz, Table of n, a(n) for n = 1..65536

Formula

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

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

a(n) >= A317241(n).

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

Example

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

Maple

a:= proc(n) option remember; `if`(n=1, 1,
      add(a((n-1)/p), p=numtheory[factorset](n-1)))
    end:
seq(a(n), n=1..200);

Mathematica

pp[n_] := pp[n] = FactorInteger[n][[All, 1]];
q[n_] := q[n] = Switch[n, 1, True, 2, False, _, AnyTrue[pp[n-1], q[(n-1)/#]&]];
a[n_] := a[n] = Which[n == 1, 1, !q[n], 0, True, Sum[a[(n-1)/p], {p, pp[n-1]}]];
Array[a, 105] (* Jean-François Alcover, Jul 14 2021, after Alois P. Heinz *)

Crossrefs

Cf. A180337, A317241, A317384.

Sequence in context: A366779 A326775 A349410 * A348444 A326620 A353372

Adjacent sequences: A317237 A317238 A317239 * A317241 A317242 A317243

Keyword

nonn

Author

Alois P. Heinz, Jul 24 2018

Status

approved