login
A339509
Number of subsets of {1..n} whose elements have the same greatest prime factor.
2
1, 2, 3, 4, 6, 7, 9, 10, 14, 18, 20, 21, 29, 30, 32, 36, 44, 45, 61, 62, 70, 74, 76, 77, 109, 125, 127, 191, 199, 200, 232, 233, 249, 253, 255, 271, 399, 400, 402, 406, 470, 471, 503, 504, 512, 640, 642, 643, 899, 963, 1219, 1223, 1231, 1232, 1744, 1760, 1888
OFFSET
0,2
LINKS
Eric Weisstein's World of Mathematics, Greatest Prime Factor
EXAMPLE
a(8) = 14 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {2, 4}, {2, 8}, {3, 6}, {4, 8} and {2, 4, 8}.
MAPLE
b:= proc(n) option remember; `if`(n<2, 0,
b(n-1)+x^max(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..70); # Alois P. Heinz, Dec 07 2020
MATHEMATICA
b[n_] := b[n] = If[n < 2, 0,
b[n - 1] + x^Max[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, 70}] (* Jean-François Alcover, Jul 09 2021, after Alois P. Heinz *)
PROG
(Python)
from sympy import primefactors
def test(n):
if n<2: return n
return max(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(57)]) # Michael S. Branicky, Dec 11 2020
CROSSREFS
Sequence in context: A071689 A187092 A076679 * A060233 A235203 A187102
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Dec 07 2020
EXTENSIONS
a(24)-a(56) from Alois P. Heinz, Dec 07 2020
STATUS
approved