OFFSET
0,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..6643
Eric Weisstein's World of Mathematics, Least Prime Factor
FORMULA
a(n) ~ 2^(n/2) if n is even and a(n) ~ 2^((n-1)/2) if n is odd. - Vaclav Kotesovec, Jul 10 2021
EXAMPLE
a(6) = 11 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {2, 4}, {2, 6}, {4, 6} and {2, 4, 6}.
MAPLE
b:= proc(n) option remember; `if`(n<2, 0,
b(n-1)+x^min(numtheory[factorset](n)))
end:
a:= n-> `if`(n<2, n+1, (p-> 2+add(2^
coeff(p, x, i)-1, i=2..degree(p)))(b(n))):
seq(a(n), n=0..60); # Alois P. Heinz, Dec 07 2020
MATHEMATICA
b[n_] := b[n] = If[n<2, 0, b[n-1] + x^Min[FactorInteger[n][[All, 1]]]];
a[n_] := If[n<2, n+1, Function[p, 2+Sum[2^Coefficient[p, x, i]-1, {i, 2, Exponent[p, x]}]][b[n]]];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jul 10 2021, after Alois P. Heinz *)
PROG
(Python)
from sympy import primefactors
def test(n):
if n<2: return n
return min(primefactors(n))
def a(n):
tests = [test(i) for i in range(n+1)]
return sum(2**tests.count(v)-1 for v in set(tests))
print([a(n) for n in range(44)]) # Michael S. Branicky, Dec 07 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Dec 07 2020
EXTENSIONS
a(24)-a(43) from Alois P. Heinz, Dec 07 2020
STATUS
approved