A033150 -id:A033150 - cp's OEIS frontend

A382476 Numbers k where record low values occur for abs(A129132(k)/k - c) = abs(A380264(k)/A380265(k) - c), where c = A033150 is Niven's constant.

1, 2, 3, 4, 8, 9, 16, 18, 20, 24, 25, 27, 28, 32, 56, 64, 81, 128, 162, 176, 192, 256, 352, 384, 736, 768, 896, 1026, 1029, 1056, 1280, 1792, 1863, 1864, 1928, 2052, 2058, 2064, 2080, 2304, 2432, 2560, 2944, 3776, 4376, 4384, 4480, 4482, 5104, 5120, 5121, 5125

Offset: 1

Amiram Eldar, Mar 28 2025

nonn

First differs from A382475 at n = 72: a(72) = 39937 while A382475(72) = 39936.

Since lim_{k->oo} A129132(k)/k = c, this sequence is infinite if Niven's constant is irrational.

Amiram Eldar, Table of n, a(n) for n = 1..103

Cf. A033150, A051903, A129132, A380264, A380265, A382475.

f[k_] := Max[FactorInteger[k][[;; , 2]]]; f[1] = 0; seq[lim_] := Module[{Niven = 1 + NSum[1 - 1/Zeta[k], {k, 2, Infinity}, NSumTerms -> 100, WorkingPrecision -> 50], dm = 2, d, s = {}, sum = 0}, Do[sum += f[k]; d = Abs[sum/k - Niven]; If[d < dm, dm = d; AppendTo[s, k]], {k, 1, lim}]; s]; seq[10^4]

default(realprecision, 120);
f(k) = if(k == 1, 0, vecmax(factor(k)[, 2]));
list(lim) = {my(niven = 1 + suminf(k = 2, 1-1/zeta(k)), dm = 2, d, s = List(), sm = 0); for(k = 1, lim, sm += f(k); d = abs(sm/k - niven); if(d < dm, dm = d; listput(s, k))); Vec(s);}

A051903 Maximum exponent in the prime factorization of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 5, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 4, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 4, 4, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 5, 1, 2, 2, 2, 1, 1, 1, 3, 1

Offset: 1

Labos Elemer, Dec 16 1999

Smallest number of factors of all factorizations of n into squarefree numbers, see also A128651, A001055. - Reinhard Zumkeller, Mar 30 2007
Maximum number of invariant factors among abelian groups of order n. - Álvar Ibeas, Nov 01 2014
a(n) is the highest of the frequencies of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1..r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24) = 3; indeed, the partition having Heinz number 24 = 2*2*2*3 is [1,1,1,2], where the distinct parts 1 and 2 have frequencies 3 and 1, respectively. - Emeric Deutsch, Jun 04 2015
From Thomas Ordowski, Dec 02 2019: (Start)
a(n) is the smallest k such that b^(phi(n)+k) == b^k (mod n) for all b.
The Euler phi function can be replaced by the Carmichael lambda function.
Problems:
(*) Are there composite numbers n > 4 such that n == a(n) (mod phi(n))? By Lehmer's totient conjecture, there are no such squarefree numbers.
(**) Are there odd numbers n such that a(n) > 1 and n == a(n) (mod lambda(n))? These are odd numbers n such that a(n) > 1 and b^n == b^a(n) (mod n) for all b.
(***) Are there odd numbers n such that a(n) > 1 and n == a(n) (mod ord_{n}(2))? These are odd numbers n such that a(n) > 1 and 2^n == 2^a(n) (mod n).
Note: if (***) do not exist, then (**) do not exist. (End)
Niven (1969) proved that the asymptotic mean of this sequence is 1 + Sum_{j>=2} 1 - (1/zeta(j)) (A033150). - Amiram Eldar, Jul 10 2020

			For n = 72 = 2^3*3^2, a(72) = max(exponents) = max(3,2) = 3.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
Benjamin Merlin Bumpus and Zoltan A. Kocsis, Spined categories: generalizing tree-width beyond graphs, arXiv:2104.01841 [math.CO], 2021.
Cao Hui-Zhong, The Asymptotic Formulas Related to Exponents in Factoring Integers, Math. Balkanica, Vol. 5 (1991), Fasc. 2.
Ivan Niven, Averages of Exponents in Factoring Integers, Proc. Amer. Math. Soc., Vol. 22, No. 2 (1969), pp. 356-360.
Eric Weisstein's World of Mathematics, Niven's Constant.
Index entries for sequences computed from exponents in factorization of n

Average value is A033150 = 1.7052....

Cf. A002322, A005361, A008479, A028234, A051904, A052409, A067029, A091050, A129132, A327295, A328310, A329885.

a051903 1 = 0
a051903 n = maximum $ a124010_row n -- Reinhard Zumkeller, May 27 2012

A051903 := proc(n)
        a := 0 ;
        for f in ifactors(n)[2] do
                a := max(a,op(2,f)) ;
        end do:
        a ;
end proc: # R. J. Mathar, Apr 03 2012
# second Maple program:
a:= n-> max(0, seq(i[2], i=ifactors(n)[2])):
seq(a(n), n=1..120);  # Alois P. Heinz, May 09 2020

Table[If[n == 1, 0, Max @@ Last /@ FactorInteger[n]], {n, 100}] (* Ray Chandler, Jan 24 2006 *)

a(n)=if(n>1,vecmax(factor(n)[,2]),0) \\ Charles R Greathouse IV, Oct 30 2012

from sympy import factorint
def A051903(n):
    return max(factorint(n).values()) if n > 1 else 0
# Chai Wah Wu, Jan 03 2015

;; With memoization-macro definec.
(definec (A051903 n) (if (= 1 n) 0 (max (A067029 n) (A051903 (A028234 n))))) ;; Antti Karttunen, Aug 08 2016

a(n) = max_{k=1..A001221(n)} A124010(n,k). - Reinhard Zumkeller, Aug 27 2011
a(1) = 0; for n > 1, a(n) = max(A067029(n), a(A028234(n))). - Antti Karttunen, Aug 08 2016
Conjecture: a(n) = a(A003557(n)) + 1. This relation together with a(1) = 0 defines the sequence. - Velin Yanev, Sep 02 2017
Comment from David J. Seal, Sep 18 2017: (Start)
This conjecture seems very easily provable to me: if the factorization of n is p1^k1 * p2^k2 * ... * pm^km, then the factorization of the largest squarefree divisor of n is p1 * p2 * ... * pm. So the factorization of A003557(n) is p1^(k1-1) * p2^(k2-1) * ... * pm^(km-1) if exponents of zero are allowed, or with the product terms that have an exponent of zero removed if they're not (if that results in an empty product, consider it to be 1 as usual).
The formula then follows from the fact that provided all ki >= 1, Max(k1, k2, ..., km) = Max(k1-1, k2-1, ..., km-1) + 1, and Max(k1-1, k2-1, ..., km-1) is not altered by removing the ki-1 values that are 0, provided we treat the empty Max() as being 0. That proves the formula and the provisos about empty products and Max() correspond to a(1) = 0.
Also, for any n, applying the formula Max(k1, k2, ..., km) times to n = p1^k1 * p2^k2 * ... * pm^km reduces all the exponents to zero, i.e., to the case a(1) = 0, so that case and the formula generate the sequence. (End)
Sum_{k=1..n} (-1)^k * a(k) ~ c * n, where c = Sum_{k>=2} 1/((2^k-1)*zeta(k)) = 0.44541445377638761933... . - Amiram Eldar, Jul 28 2024
a(n) <= log(n)/log(2). - Hal M. Switkay, Jul 03 2025

A090699 Decimal expansion of the Erdos-Szekeres constant zeta(3/2)/zeta(3).

Original entry on oeis.org

2, 1, 7, 3, 2, 5, 4, 3, 1, 2, 5, 1, 9, 5, 5, 4, 1, 3, 8, 2, 3, 7, 0, 8, 9, 8, 4, 0, 4, 3, 8, 2, 2, 3, 7, 2, 2, 9, 0, 6, 7, 1, 1, 3, 2, 9, 1, 3, 1, 6, 6, 0, 8, 5, 6, 7, 4, 9, 1, 7, 5, 7, 5, 8, 9, 6, 7, 0, 5, 9, 6, 6, 1, 7, 2, 6, 6, 4, 4, 4, 6, 8, 2, 0, 3, 7, 8, 5, 7, 2, 7, 8, 3, 8, 3, 1, 7, 6, 5, 1, 0, 2, 6, 6, 4

Offset: 1

Benoit Cloitre, Jan 14 2004

Let N(x) denotes the number of 2-full integers not exceeding x. Then lim_{x->oo} N(x)/sqrt(x) = zeta(3/2)/zeta(3). Also related to Niven's constant.

			zeta(3/2)/zeta(3) = 2.17325431251955413823708984...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 112-114.

S. W. Golomb, Powerful numbers, Amer. Math. Monthly, Vol. 77 (1970), 848-852.
Ivan Niven, Averages of Exponents in Factoring Integers, Proc. Amer. Math. Soc., Vol. 22, No. 2 (1969), pp. 356-360.

Cf. A001694 (powerful numbers), A102834 (nonsquare powerful numbers).

Cf. A033150, A051904.

RealDigits[N[Zeta[3/2]/Zeta[3],150]][[1]] (* T. D. Noe, May 03 2006 *)

zeta(3/2)/zeta(3) \\ Michel Marcus, Oct 06 2017

Product_{p prime} (1+1/p^(3/2)) = zeta(3/2)/zeta(3). - T. D. Noe, May 03 2006

Equals lim_{n->oo} (Sum_{k=1..n} A051904(k) - n)/sqrt(n) (Niven, 1969). - Amiram Eldar, Jul 11 2020

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, May 16 2007

A129132 Partial sums of A051903.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 7, 10, 12, 13, 14, 16, 17, 18, 19, 23, 24, 26, 27, 29, 30, 31, 32, 35, 37, 38, 41, 43, 44, 45, 46, 51, 52, 53, 54, 56, 57, 58, 59, 62, 63, 64, 65, 67, 69, 70, 71, 75, 77, 79, 80, 82, 83, 86, 87, 90, 91, 92, 93, 95, 96, 97, 99, 105, 106, 107, 108, 110, 111, 112

Offset: 1

Reinhard Zumkeller, Mar 30 2007

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A007947, A033150, A051903, A128651.

f[1] = 0; f[n_] := Max @ FactorInteger[n][[;; , 2]]; Accumulate @ Array[f, 70] (* Amiram Eldar, Oct 19 2020 *)

a(n+1) = a(n) + A051903(n), a(1) = 0;
A128651(a(n-1) + 2) = A007947(n) for n>1.
a(n) ~ c * n, where c is Niven's constant (A033150). - Amiram Eldar, Oct 19 2020
a(n) = - Sum_{i=2..n} Sum_{j=1..n} mobius(i)*floor(n/(i^j)). - Ridouane Oudra, Nov 22 2024

A368711 The maximal exponent in the prime factorization of the exponentially odd numbers (A268335).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1

Offset: 1

Amiram Eldar, Jan 04 2024

Differs from A368472 at n = 1, 154, 610, 707, 762, ... .

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A033150, A051903, A268335, A368472.

Similar sequences: A368710, A368712, A368713.

f[n_] := Module[{e = FactorInteger[n][[;; , 2]]}, If[AllTrue[e, OddQ], Max @@ e, Nothing]]; f[1] = 0; Array[f, 150]

lista(kmax) = {my(e); print1(0, ", "); for(k = 2, kmax, e = factor(k)[,2]; if(vecprod(e)%2, print1(vecmax(e), ", ")));}

a(n) = A051903(A268335(n)).
a(n) is odd for n >= 2.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1 + 2 * Sum_{k>=1} (1 - Product_{p prime} (1 - 1/(p^(2*k-1)*(p^2+p-1)))) = 1.34877064483679975726... .

A383156 The sum of the maximum exponents in the prime factorizations of the divisors of n.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 6, 3, 3, 1, 7, 1, 3, 3, 10, 1, 7, 1, 7, 3, 3, 1, 13, 3, 3, 6, 7, 1, 7, 1, 15, 3, 3, 3, 13, 1, 3, 3, 13, 1, 7, 1, 7, 7, 3, 1, 21, 3, 7, 3, 7, 1, 13, 3, 13, 3, 3, 1, 15, 1, 3, 7, 21, 3, 7, 1, 7, 3, 7, 1, 22, 1, 3, 7, 7, 3, 7, 1, 21, 10, 3, 1

Offset: 1

Amiram Eldar, Apr 18 2025

Inverse Möbius transform of A051903.

a(n) depends only on the prime signature of n (A118914).

			4 has 3 divisors: 1, 2 = 2^1 and 4 = 2^2. The maximum exponents in their prime factorizations are 0, 1 and 2, respectively. Therefore, a(4) = 0 + 1 + 2 = 3.
12 has 6 divisors: 1, 2 = 2^1, 3 = 3^1, 4 = 2^2, 6 = 2 * 3 and 12 = 2^2 * 3. The maximum exponents in their prime factorizations are 0, 1, 1, 2, 1 and 2, respectively. Therefore, a(12) = 0 + 1 + 1 + 2 + 1 + 2 = 7.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Amiram Eldar, Plot of Sum_{k=1..n} a(k)/(c_1*n*log(n) + c_2*n) - 1 for n = 10^(1..10).

Cf. A000005, A001221, A005117, A034444, A051903, A073184, A118914, A252505, A309307, A383157, A383158, A383159.

Cf. A001620, A013661, A033150, A306016.

emax[n_] := If[n == 1, 0, Max[FactorInteger[n][[;; , 2]]]]; a[n_] := DivisorSum[n, emax[#] &]; Array[a, 100]
(* second program: *)
a[n_] := If[n == 1, 0, Module[{e = FactorInteger[n][[;; , 2]], emax, v}, emax = Max[e]; v = Table[Times @@ (Min[# + 1, k + 1] & /@ e), {k, 1, emax}]; v[[1]] + Sum[k*(v[[k]] - v[[k - 1]]), {k, 2, emax}] - 1]]; Array[a, 100]

emax(n) = if(n == 1, 0, vecmax(factor(n)[,2]));
a(n) = sumdiv(n, d, emax(d));

a(n) = if(n == 1, 0, my(e = factor(n)[, 2], emax = vecmax(e), v); v = vector(emax, k, vecprod(apply(x ->min(x+1 , k+1), e))); v[1] + sum(k = 2, emax, k * (v[k]-v[k-1])) - 1);

a(n) = Sum_{d|n} A051903(d).
a(n) = A000005(n) * A383157(n)/A383158(n).
a(p^e) = e*(e+1)/2 for prime p and e >= 0. In particular, a(p) = 1 for prime p.
a(n) = 2^omega(n) - 1 = A309307(n) if n is squarefree (A005117).
a(n) = tau(n, 2) - 1 + Sum_{k=2..A051903(n)} k * (tau(n, k+1) - tau(n, k)), where tau(n, k) is the number of k-free divisors of n (k-free numbers are numbers that are not divisible by a k-th power other than 1). For a given k >= 2, tau(n, k) is a multiplicative function with tau(p^e, k) = min(e+1, k). E.g., tau(n, 2) = A034444(n), tau(n, 3) = A073184(n), and tau(n, 4) = A252505(n).
Sum_{k=1..n} a(k) ~ c_1 * n * log(n) + c_2 * n, where c_1 is Niven's constant (A033150), c_2 = -1 + (2*gamma - 1)*c_1 - 2*zeta'(2)/zeta(2)^2 - Sum_{k>=3} (k-1) * (k*zeta'(k)/zeta(k)^2 - (k-1)*zeta'(k-1)/zeta(k-1)^2) = -2.37613633493572231366..., and gamma is Euler's constant (A001620).

A368712 The maximal exponent in the prime factorization of the cubefree numbers.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1

Offset: 1

Amiram Eldar, Jan 04 2024

The asymptotic density of occurrences of 1 is zeta(3)/zeta(2) = 0.730762... (A253905), and the asymptotic density of occurrences of 2 is 1 - zeta(3)/zeta(2) = 0.269237... .

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A004709, A005117, A008966, A013929, A033150, A051903, A067259.
Cf. A002117, A013661, A253905.
Similar sequences: A368710, A368711, A368713.

s[n_] := If[n == 1, 0, Max @@ Last /@ FactorInteger[n]]; s /@ Select[Range[100], Max[FactorInteger[#][[;; , 2]]] < 3 &]
(* or *)
f[n_] := Module[{e = Max @@ FactorInteger[n][[;; , 2]]}, If[e < 3, e, Nothing]]; f[1] = 0; Array[f, 100]

lista(kmax) = {my(e); print1(0, ", "); for(k = 2, kmax, e = vecmax(factor(k)[,2]); if(e < 3, print1(e, ", ")));}

from sympy import mobius, integer_nthroot, factorint
def A368712(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**3) for k in range(1, integer_nthroot(x,3)[0]+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return max(factorint(m).values(),default=0) # Chai Wah Wu, Aug 12 2024

a(n) = A051903(A004709(n)).
a(n) = 2 - A008966(A004709(n)) for n >= 2.
Except for n = 1, a(n) = 1 or 2.
a(n) = 1 if and only if A004709(n) is squarefree (A005117).
a(n) = 2 if and only if A004709(n) > 1 and is nonsquarefree (A013929), i.e., A004709(n) is in A067259.
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2 - zeta(3)/zeta(2) = 2 - A253905 = 1.269237030598... .

A368710 The maximal exponent in the prime factorization of the powerful numbers.

Original entry on oeis.org

0, 2, 3, 2, 4, 2, 3, 5, 2, 2, 6, 3, 4, 2, 3, 2, 3, 7, 4, 2, 2, 3, 3, 2, 5, 8, 5, 2, 4, 3, 2, 3, 4, 4, 2, 2, 3, 9, 2, 6, 4, 4, 3, 2, 6, 4, 5, 2, 5, 2, 2, 3, 5, 3, 10, 2, 3, 7, 2, 2, 4, 3, 3, 3, 2, 3, 2, 2, 5, 6, 2, 6, 2, 3, 2, 4, 5, 4, 4, 11, 2, 7, 3, 2, 8, 3, 4

Offset: 1

Amiram Eldar, Jan 04 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
Rafael Jakimczuk, Generalizations of the Niven constant and the Feller-Tornier constant, International Mathematical Forum, Vol. 13, No. 9 (2018), pp. 415-425.

Cf. A001694, A033150, A048250, A051903, A059956, A090699.

Similar sequences: A368711, A368712, A368713.

s[n_] := If[n == 1, 0, Max @@ Last /@ FactorInteger[n]]; s /@ Select[Range[3000], # == 1 || Min[FactorInteger[#][[;;, 2]]] > 1 &]
(* or *)
f[n_] := Module[{e = FactorInteger[n][[;; , 2]]}, If[n == 1, 0, If[Min[e] > 1, Max[e], Nothing]]]; Array[f, 3000]

lista(kmax) = {my(e); for(k = 1, kmax, e = factor(k)[,2]; if(k == 1, print1(0, ", "), if(vecmin(e) > 1, print1(vecmax(e), ", "))));}

a(n) = A051903(A001694(n)).
a(n) >= 2 for n >= 2.
Sum_{a(n)<=x} = D_{2,1} * sqrt(x) + O(sqrt(x)), where D_{2,1} = (6/Pi^2) * (2 + Sum_{k>=1} (A051903(k)+2)/(sqrt(k) * A048250(k))) (Jakimczuk, 2018; Theorem 2.1 and Remark 2.3).
Asymptotic mean (consequence of the formula above): Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = D_{2,1} * zeta(3)/zeta(3/2) = D_{2,1} / A090699.
The sum in the formula for D_{2,1} converges slowly: for k up to 10^8, 10^9 and 10^10 the sums are 14.845..., 14.908... and 14.938..., respectively. Thus, a lower bound for the value of this mean, calculated by summing over k=1..10^10, is 4.738... .

A375039 The maximum exponent in the prime factorization of 2*n-1.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1

Offset: 1

Amiram Eldar, Jul 28 2024

Bisection of A051903.

Cf. A033150, A375040.

a[n_] := Max[FactorInteger[2*n - 1][[;; , 2]]]; a[1] = 0; Array[a, 100]

a(n) = if(n == 1, 0, vecmax(factor(2*n-1)[,2]));

a(n) = A051903(2*n-1).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1 + Sum_{k>=2} (1 - 1/((1-1/2^k) * zeta(k))) = 1.25979668632898014495... .

A384655 a(n) = Sum_{k=1..n} A051903(gcd(n,k)).

Original entry on oeis.org

0, 1, 1, 3, 1, 4, 1, 7, 4, 6, 1, 11, 1, 8, 7, 15, 1, 14, 1, 17, 9, 12, 1, 25, 6, 14, 13, 23, 1, 22, 1, 31, 13, 18, 11, 36, 1, 20, 15, 39, 1, 30, 1, 35, 26, 24, 1, 53, 8, 32, 19, 41, 1, 44, 15, 53, 21, 30, 1, 59, 1, 32, 34, 63, 17, 46, 1, 53, 25, 46, 1, 81, 1, 38

Offset: 1

Amiram Eldar, Jun 06 2025

nonn

The terms of this sequence can be calculated efficiently using the 1st formula. The value the of function f(n, k) is equal to the number of integers i from 1 to n such that gcd(i, n) is 1 if k = 1, or k-free if k >= 2 (k-free numbers are numbers that are not divisible by a k-th power other than 1). E.g., f(n, 1) = A000010(n), f(n, 2) = A063659(n), and f(n, 3) = A254926(n).

			a(4) = A051903(gcd(4,1)) + A051903(gcd(4,2)) + A051903(gcd(4,3)) + A051903(gcd(4,4)) = A051903(1) + A051903(2) + A051903(1) + A051903(4) = 0 + 1 + 0 + 2 = 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A033150, A005117, A050873, A051903, A051953, A063659, A067259, A254926, A357310, A383156, A384656 (unitary analog).

e[n_] := If[n == 1, 0, Max[FactorInteger[n][[;;, 2]]]]; a[n_] := Sum[e[GCD[n, k]], {k, 1, n}]; Array[a, 100]
(* or *)
f[p_, e_, k_] := p^e - If[e < k, 0, p^(e - k)]; a[n_] := Module[{fct = FactorInteger[n], emax, s}, emax = Max[fct[[;; , 2]]]; s = emax * n; Do[s -= Times @@ (f[#1, #2, k] & @@@ fct), {k, 1, emax}]; s]; a[1] = 0; Array[a, 100]

e(n) = if(n == 1, 0, vecmax(factor(n)[,2]));
a(n) = sum(k = 1, n, e(gcd(n, k)));

a(n) = if(n == 1, 0, my(f = factor(n), p = f[,1], e = f[,2], emax = vecmax(e), s = emax*n); for(k = 1, emax, s -= prod(i = 1, #p, p[i]^e[i] - if(e[i] < k, 0, p[i]^(e[i]-k)))); s);

a(n) = Sum_{k=1..A051903(n)} (n - f(n, k)) = A051903(n) * n  - Sum_{k=1..A051903(n)} f(n, k), where f(n, k) is multiplicative for a given k, with f(p^e, k) = p^e - p^(e-k) if e >= k and f(p^e, k) = p^e if e < k.
a(n) = 1 if and only if n is prime.
a(n) >= 2 if and only if n is composite.
a(n) >= A051953(n) with equality if and only if n is squarefree.
a(n) >= 2*n - A000010(n) - A063659(n) with equality if and only if n is cubefree that is not squarefree (i.e., n in A067259, or equivalently, A051903(n) = 2).
a(p^e) = (p^e-1)/(p-1) for a prime p and e >= 1.
a(n) < c*n and lim sun_{n->oo} a(n)/n = c, where c is Niven's constant (A033150).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Sum{k>=1} (1-1/zeta(2*k)) = 0.49056393035179738598... .

cp's OEIS Frontend

A382476 Numbers k where record low values occur for abs(A129132(k)/k - c) = abs(A380264(k)/A380265(k) - c), where c = A033150 is Niven's constant.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A051903 Maximum exponent in the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Formula

A090699 Decimal expansion of the Erdos-Szekeres constant zeta(3/2)/zeta(3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A129132 Partial sums of A051903.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A368711 The maximal exponent in the prime factorization of the exponentially odd numbers (A268335).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A383156 The sum of the maximum exponents in the prime factorizations of the divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A368712 The maximal exponent in the prime factorization of the cubefree numbers.

Views

Author

Keywords

Comments

Links