%I #76 Aug 16 2024 16:41:45
%S 1,2,2,3,2,5,2,4,3,6,2,8,2,6,5,5,2,10,2,8,5,7,2,11,3,7,4,8,2,18,2,6,6,
%T 8,5,14,2,8,6,11,2,19,2,9,8,8,2,15,3,12,6,9,2,16,5,11,6,8,2,26,2,8,8,
%U 7,5,22,2,10,6,20,2,18,2,9,9,10,5,23,2,14,5,9,2,28,5,9,7,11,2,32,5,10
%N Number of numbers <= n whose set of prime factors is a subset of the set of prime factors of n.
%C This function of n appears in an ABC-conjecture by Andrew Granville. See Goldfeld. - _T. D. Noe_, Jun 30 2009
%H Michael De Vlieger, <a href="/A010846/b010846.txt">Table of n, a(n) for n = 1..10000</a> (first 5000 terms from T. D. Noe)
%H Dorian Goldfeld, <a href="http://www.math.columbia.edu/~goldfeld/ABC-Conjecture.pdf">Modular forms, elliptic curves, and the ABC conjecture</a>
%F a(n) = |{k<=n, k|n^(tau(k)-1)}|. - _Vladeta Jovovic_, Sep 13 2006
%F a(n) = Sum_{j = 1..n} Product_{primes p | j} delta(n mod p,0) where delta is the Kronecker delta. - _Robert Israel_, Feb 09 2015
%F a(n) = Sum_{1<=k<=n,(n,k)=1} mu(k)*floor(n/k). - _Benoit Cloitre_, May 07 2016
%F a(n) = Sum_{k=1..n} floor(n^k/k)-floor((n^k -1)/k). - _Anthony Browne_, May 28 2016
%e From _Wolfdieter Lang_, Jun 30 2014: (Start)
%e a(1) = 1 because the empty set is a subset of any set.
%e a(6) = 5 from the five numbers: 1 with the empty set, 2 with the set {2}, 3 with {3}, 4 with {2} and 6 with {2,3}, which are all subsets of {2,3}. 5 is out because {5} is not a subset of {2,3}. (End)
%e From _David A. Corneth_, Feb 10 2015: (Start)
%e Let p# be the product of primes up to p, A002110. Then,
%e a(13#) = 1161
%e a(17#) = 4843
%e a(19#) = 19985
%e a(23#) = 83074
%e a(29#) = 349670
%e a(31#) = 1456458
%e a(37#) = 6107257
%e a(41#) = 25547835
%e (End)
%p A:= proc(n) local F, S, s,j,p;
%p F:= numtheory:-factorset(n);
%p S:= {1};
%p for p in F do
%p S:= {seq(seq(s*p^j, j=0..floor(log[p](n/s))),s=S)}
%p od;
%p nops(S)
%p end proc;
%p seq(A(n),n=1..1000); # _Robert Israel_, Jun 27 2014
%t pf[n_] := If[n==1, {}, Transpose[FactorInteger[n]][[1]]]; SubsetQ[lst1_, lst2_] := Intersection[lst1,lst2]==lst1; Table[pfn=pf[n]; Length[Select[Range[n], SubsetQ[pf[ # ],pfn] &]], {n,100}] (* _T. D. Noe_, Jun 30 2009 *)
%t Table[Total[MoebiusMu[#] Floor[n/#] &@ Select[Range@ n, CoprimeQ[#, n] &]], {n, 92}] (* _Michael De Vlieger_, May 08 2016 *)
%o (PARI) a(n,f=factor(n)[,1])=if(#f>1,my(v=f[1..#f-1],p=f[#f],s); while(n>0, s+=a(n,v); n\=p); s, if(#f&&n>0,log(n+.5)\log(f[1])+1,n>0)) \\ _Charles R Greathouse IV_, Jun 27 2013
%o (PARI) a(n) = sum(k=1,n,if(gcd(n,k)-1,0,moebius(k)*(n\k))) \\ _Benoit Cloitre_, May 07 2016
%o (PARI) a(n,f=factor(n)[,1])=if(#f<2, return(if(#f, valuation(n,f[1])+1, 0))); my(v=f[1..#f-1],p=f[#f],s); while(n, s+=a(n,v); n\=p); s \\ _Charles R Greathouse IV_, Nov 03 2021
%o (Python)
%o def A010846(n): return sum((m:=n**k)//k-(m-1)//k for k in range(1,n+1)) # _Chai Wah Wu_, Aug 15 2024
%Y Cf. A162306 (numbers for each n).
%K nonn,easy
%O 1,2
%A _Olivier GĂ©rard_
%E Definition made more precise at the suggestion of _Wolfdieter Lang_