|
%I #22 Jul 10 2021 16:21:22
%S 1,2,3,4,6,7,11,12,20,22,38,39,71,72,136,140,268,269,525,526,1038,
%T 1046,2070,2071,4119,4121,8217,8233,16425,16426,32810,32811,65579,
%U 65611,131147,131151,262223,262224,524368,524432,1048720,1048721,2097297,2097298
%N Number of subsets of {1..n} whose elements have the same smallest prime factor.
%H Alois P. Heinz, <a href="/A339510/b339510.txt">Table of n, a(n) for n = 0..6643</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LeastPrimeFactor.html">Least Prime Factor</a>
%F 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
%e a(6) = 11 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {2, 4}, {2, 6}, {4, 6} and {2, 4, 6}.
%p b:= proc(n) option remember; `if`(n<2, 0,
%p b(n-1)+x^min(numtheory[factorset](n)))
%p end:
%p a:= n-> `if`(n<2, n+1, (p-> 2+add(2^
%p coeff(p, x, i)-1, i=2..degree(p)))(b(n))):
%p seq(a(n), n=0..60); # _Alois P. Heinz_, Dec 07 2020
%t b[n_] := b[n] = If[n<2, 0, b[n-1] + x^Min[FactorInteger[n][[All, 1]]]];
%t a[n_] := If[n<2, n+1, Function[p, 2+Sum[2^Coefficient[p, x, i]-1, {i, 2, Exponent[p, x]}]][b[n]]];
%t Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Jul 10 2021, after _Alois P. Heinz_ *)
%o (Python)
%o from sympy import primefactors
%o def test(n):
%o if n<2: return n
%o return min(primefactors(n))
%o def a(n):
%o tests = [test(i) for i in range(n+1)]
%o return sum(2**tests.count(v)-1 for v in set(tests))
%o print([a(n) for n in range(44)]) # _Michael S. Branicky_, Dec 07 2020
%Y Cf. A020639, A339509.
%K nonn
%O 0,2
%A _Ilya Gutkovskiy_, Dec 07 2020
%E a(24)-a(43) from _Alois P. Heinz_, Dec 07 2020
|
