OFFSET
1,2
COMMENTS
This function of n appears in an ABC-conjecture by Andrew Granville. See Goldfeld. - T. D. Noe, Jun 30 2009
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 5000 terms from T. D. Noe)
Dorian Goldfeld, Modular forms, elliptic curves, and the ABC conjecture
FORMULA
a(n) = |{k<=n, k|n^(tau(k)-1)}|. - Vladeta Jovovic, Sep 13 2006
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
a(n) = Sum_{1<=k<=n,(n,k)=1} mu(k)*floor(n/k). - Benoit Cloitre, May 07 2016
a(n) = Sum_{k=1..n} floor(n^k/k)-floor((n^k -1)/k). - Anthony Browne, May 28 2016
EXAMPLE
From Wolfdieter Lang, Jun 30 2014: (Start)
a(1) = 1 because the empty set is a subset of any set.
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)
MAPLE
A:= proc(n) local F, S, s, j, p;
F:= numtheory:-factorset(n);
S:= {1};
for p in F do
S:= {seq(seq(s*p^j, j=0..floor(log[p](n/s))), s=S)}
od;
nops(S)
end proc;
seq(A(n), n=1..1000); # Robert Israel, Jun 27 2014
MATHEMATICA
pf[n_] := If[n == 1, {}, Transpose[FactorInteger[n]][[1]] ]; fQ[lst1_, lst2_] := Intersection[lst1, lst2] == lst1; Table[pfn = pf[n]; Count[Range[n], _?(fQ[pf[#], pfn] &)], {n, 100}] (* T. D. Noe, Jun 30 2009, corrected by Michael De Vlieger, Jul 19 2026 *)
(* Alternative: *)
f[x_] := Module[{c, m , j, k, nn, v , p , s, t, z}, s = Boole[x <= 0]; nn = Abs[x]; If[nn == 1, c = 1, z = Length@ MapIndexed[Set[{p[#2], m[#2]}, {#1, s}] & @@ {#1, First[#2]} &, FactorInteger[nn][[All, 1]] ]; k = Times @@ Array[p[#]^m[#] &, z]; Set[{c, v, t}, {0, 1, False}]; Do[Set[t, k > nn]; If[t, k /= p[v]^(m[v] - s); m[v] = s; v++; If[v > z, Break[] ], v = 1; c++ ]; m[v]++; k *= p[v], {i, Infinity}]]; c]; Array[f, 120] (* Michael De Vlieger, Jul 19 2026 *)
PROG
(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, logint(n, f[1])+1, n>0)) \\ Charles R Greathouse IV, Jun 27 2013
(PARI) a(n) = sum(k=1, n, if(gcd(n, k)-1, 0, moebius(k)*(n\k))) \\ Benoit Cloitre, May 07 2016
(PARI) a(n, f=factor(n)[, 1])=if(#f<2, return(if(#f, logint(n, f[1])+1, n>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 [corrected by Daniel Suteu, May 14 2026]
(Python)
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
(Python)
from math import gcd
from sympy import mobius
def A010846(n): return sum(mobius(k)*(n//k) for k in range(1, n+1) if gcd(n, k)==1) # Chai Wah Wu, Apr 23 2025
(Python)
from functools import lru_cache
from sympy import primefactors, integer_log
def A010846(n):
if n == 1: return 1
ps = tuple(sorted(primefactors(n)))
@lru_cache(maxsize=None)
def g(x, m): return 1 if x == 1 else sum(g(x//ps[m]**i, m-1) for i in range(integer_log(x, ps[m])[0]+1)) if m else integer_log(x, ps[0])[0]+1
return g(n, len(ps)-1) # Chai Wah Wu, Apr 05 2026
CROSSREFS
KEYWORD
nonn,easy,changed
AUTHOR
EXTENSIONS
Definition made more precise at the suggestion of Wolfdieter Lang, Jun 30 2014
Example that has since become its own sequence deleted by Peter Munn, Jul 19 2026
STATUS
approved