|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
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))):
|
|
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]]];
|
|
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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|