login
A339510
Number of subsets of {1..n} whose elements have the same smallest prime factor.
2
1, 2, 3, 4, 6, 7, 11, 12, 20, 22, 38, 39, 71, 72, 136, 140, 268, 269, 525, 526, 1038, 1046, 2070, 2071, 4119, 4121, 8217, 8233, 16425, 16426, 32810, 32811, 65579, 65611, 131147, 131151, 262223, 262224, 524368, 524432, 1048720, 1048721, 2097297, 2097298
OFFSET
0,2
LINKS
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
Sequence in context: A325769 A360955 A226538 * A191930 A202113 A113243
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Dec 07 2020
EXTENSIONS
a(24)-a(43) from Alois P. Heinz, Dec 07 2020
STATUS
approved