A109395 -id:A109395 - cp's OEIS frontend

A259850 Numbers k such that k/phi(k) equals sigma(x)/x for some x<=k.

1, 3, 8, 9, 14, 15, 16, 21, 26, 27, 28, 32, 40, 45, 50, 52, 56, 63, 64, 75, 80, 81, 98, 100, 104, 112, 128, 130, 135, 144, 147, 160, 162, 182, 189, 192, 196, 200, 208, 216, 224, 225, 243, 250, 255, 256, 260, 288, 310, 320, 324, 338, 364, 372, 375, 384, 392, 400

Offset: 1

Michel Marcus, Jul 07 2015

nonn

This sequence is motivated by the fact that sigma(n)/n and n/phi(n) are both >= 1.
For the first few terms, we get these ratios: 1, 3/2, 2, 3/2, 7/3, 15/8, 2, ....
The ordered list of distinct values up to a given limit is:
up to 10^1: [1, 3/2, 2];
up to 10^2: [1, 3/2, 7/4, 15/8, 2, 13/6, 7/3, 5/2];
up to 10^3: [1, 3/2, 7/4, 15/8, 31/16, 255/128, 2, 13/6, 7/3, 5/2, 91/36, 31/12, 85/32, 65/24, 35/12, 3, 31/10, 13/4];
up to 10^4: [1, 3/2, 7/4, 15/8, 31/16, 255/128, 2, 13/6, 7/3, 5/2, 91/36, 31/12, 85/32, 65/24, 403/144, 1105/384, 35/12, 635/216, 2555/864, 3, 217/72, 127/42, 73/24, 31/10, 51/16, 13/4, 1651/504, 527/160, 403/120, 221/64, 7/2, 127/36, 217/60];
up to 10^5: [1, 3/2, 7/4, 15/8, 31/16, 255/128, 65535/32768, 2, 33/16, 267/128, 13/6, 7/3, 133/54, 5/2, 91/36, 31/12, 85/32, 21845/8192, 65/24, 11/4, 89/32, 403/144, 1105/384, 35/12, 635/216, 2555/864, 3, 217/72, 127/42, 73/24, 665/216, 595/192, 31/10, 19/6, 51/16, 77/24, 1397/432, 13/4, 1651/504, 527/160, 949/288, 403/120, 221/64, 7/2, 127/36, 511/144, 6851/1920, 217/60, 119/32];
tending towards the intersection of the 2 sets {sigma(n)/n} (A017665/A017666) and {n/phi(n)} (A109395/A076512).
If k is a term, then so are all numbers > k with the same set of prime factors as k. - Robert Israel, Mar 09 2023

			1/phi(1) = 1/1 = sigma(1)/1, so 1 is in the sequence.
3/phi(3) = 3/2 = sigma(2)/2, so 3 is in the sequence.
8/phi(8) = 2/1 = sigma(6)/6, so 8 is in the sequence.

Robert Israel, Table of n, a(n) for n = 1..1230

Cf. A000010, A109395, A076512.
Cf. A000203, A017665, A017666.
Primitive elements: A361363.

R:= NULL: count:= 0: V:= {}:
for k from 1 while count < 100 do
 V:= V union  {numtheory:-sigma(k)/k};
 if member(k/numtheory:-phi(k), V) then R:= R,k; count:= count+1 fi;
od:
R; # Robert Israel, Mar 08 2023

lista(nn) = {vs = vector(nn, n, sigma(n)/n); ve = vector(nn, n, n/eulerphi(n)); vr = []; for (n=1, #ve, ven = ve[n]; for (m=1, n, if ((vs[m] == ven), print1(n, ", "); break);););}

Name corrected by Michel Marcus, Nov 25 2020

A295314 a(n) = sigma(n) / gcd(sigma(n), phi(sigma(n))).

Original entry on oeis.org

1, 3, 2, 7, 3, 3, 2, 15, 13, 3, 3, 7, 7, 3, 3, 31, 3, 13, 5, 7, 2, 3, 3, 15, 31, 7, 5, 7, 15, 3, 2, 7, 3, 3, 3, 91, 19, 15, 7, 15, 7, 3, 11, 7, 13, 3, 3, 31, 19, 31, 3, 7, 3, 15, 3, 15, 5, 15, 15, 7, 31, 3, 13, 127, 7, 3, 17, 7, 3, 3, 3, 65, 37, 19, 31, 35, 3, 7, 5, 31, 11, 7, 7, 7, 3, 33, 15, 15, 15, 13, 7, 7, 2, 3

Offset: 1

Antti Karttunen, Nov 22 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000010, A000203, A009195, A109395, A295313, A295315.

a(n) = my(sn = sigma(n)); sn/gcd(sn, eulerphi(sn)); \\ Michel Marcus, Nov 23 2017

a(n) = A000203(n) / A295313(n) = A109395(A000203(n)).

A127415 a(n) = Sum_{1<=k<=n, gcd(k,n)=1}, A000217(k).

Original entry on oeis.org

1, 1, 4, 7, 20, 16, 56, 50, 93, 80, 220, 110, 364, 224, 340, 372, 816, 354, 1140, 580, 966, 880, 2024, 820, 2200, 1456, 2304, 1666, 4060, 1240, 4960, 2856, 3850, 3264, 5180, 2706, 8436, 4560, 6396, 4440, 11480, 3612, 13244, 6710, 8400, 8096, 17296, 6344, 17297, 8600

Offset: 1

Gary W. Adamson, Jan 13 2007

From Wolfdieter Lang, Jun 14 2011: (Start)
Such sums are over a reduced residue system modulo n. See the Apostol reference, p. 133, for the definition or the wikipedia link given under A189918.
This sum over triangular numbers can be found using the results given in exercise 16 of the Apostol reference on p. 48, together with the definition of phi_1(n) and phi_2(n) from the exercise 15.
The result for n >= 2 coincides with the formula given below, using Product_{p|n} (1 - p) = mu(rad(n))*rad(n)*phi(n)/n, with the definitions given there.
(End)

			a(6) = 16 since the relative primes of 6 are 1 and 5 and (1 + 15) = 16.
a(6) = (6/(3!*2))*(15*6 + 1*6)*(1/2)*(2/3)= 16.

T. Apostol, Introduction to Analytic Number Theory, Springer, 1986.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000217, A023896, A076512/A109395, A189918.

rad[n_] := Times @@ (FactorInteger[n][[ All, 1]]); a[n_] := (n/(3!*2))*((2*n+3)*n + MoebiusMu[ rad[n]]*rad[n])*(EulerPhi[n] / n); a[1] = 1; Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 03 2011 *)

a(n)=if(n<3,return(1));my(s=factor(n)[,1]); s=prod(i=1,#s,s[i]); (n/12)*((2*n+3)*n + moebius(s)*s)*(eulerphi(n)/n) \\ Charles R Greathouse IV, May 17 2011

a(n) = sum(k=1, n, if (gcd(n,k)==1, k*(k+1)/2)); \\ Michel Marcus, Feb 01 2016

M * V where M = A054521 is an infinite lower triangular matrix and V = A000217: (1, 3, 6, 10, ...).
From Wolfdieter Lang, May 17 2011: (Start)
a(n) = (n/(3!*2))*((2*n+3)*n + mu(rad(n))*rad(n))*(phi(n)/n), n >= 2, with rad(n) the squarefree kernel of n (the largest squarefree number dividing n, see A007947), the Moebius function mu(n)=A008683(n), and the Euler totient function phi(n)= A000010(n).
Note that phi(n)/n = A076512(n)/A109395(n) = phi(rad(n))/rad(n).
Proof via inclusion-exclusion.
  (End)

More terms and formula from Wolfdieter Lang, May 17 2011

More terms from Michel Marcus, Feb 01 2016

A189918 Sum of tetrahedral numbers A000292(k), with k in the reduced residue system modulo n.

Original entry on oeis.org

0, 1, 5, 11, 35, 36, 126, 130, 264, 260, 715, 406, 1365, 952, 1530, 1716, 3876, 1830, 5985, 3300, 5796, 5500, 12650, 5460, 15075, 10556, 16965, 12810, 31465, 9920, 40920, 24616, 34650, 30192, 49210, 26106, 82251, 46740, 67158, 47320

Offset: 1

Wolfdieter Lang, May 19 2011

nonn

The reduced residue system modulo n used here is the set of numbers k from the set {0,1,...,n-1} which satisfy gcd(k,n)=1. There are phi(n) = A000010(n) such numbers k. Cf. A038566. See also the Apostol reference p. 133, and the Wikipedia link.
This is the m=3 member of a family of sequences, call them rmnS(m) (reduced mod n sum), with entries rmnS(m;n):=sum(binomial(k+m-1,m),0<=k<=n-1 with gcd(k,n)=1), m>=0, n>=1. Recall gcd(0,n)=n.
The members for m=0, 1, and 2 are A000010(n), A023896(n) and A127415(n), respectively, where in the last two the offset for n=1 should be taken as 0 (not 1).

			a(6) = A000292(1) + A000292(5)= 1 + 35 = 36.
a(6) = (6*8/4!)*(6*8 + 1*6)*((1/2)*(2/3)) = 36.
a(12) = A000292(1) + A000292(5) + A000292(7) + A000292(11) = 1 + 35 + 84 + +286 = 406.
a(12) = (12*14/4!)*(12*14 + 1*6)*((1/2)*(2/3)) = 406.

T. Apostol, Introduction to Analytic Number Theory, Springer, 1986.

G. C. Greubel, Table of n, a(n) for n = 1..10000
Wikipedia, Reduced residue system

Cf. A000010, A038566, A076512/A109395, A023896, A127415.

A000292 := proc(n) binomial(n+2,3) ; end proc:
A189918 := proc(n) local a; a := 0 ; for k from 0 to n-1 do if igcd(k,n) = 1 then a := a+A000292(k); end if; end do: a ; end proc:
seq(A189918(n),n=1..40) ; # R. J. Mathar, Jun 13 2011

a[n_] := Sum[ Boole[GCD[k, n] == 1]*k*(k+1)*(k+2)/6, {k, 0, n-1}]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jul 12 2012 *)

a(n) = sum(k=0, n-1, if (gcd(n,k)==1, k*(k+1)*(k+2)/6)); \\ Michel Marcus, Feb 01 2016

a(n) = Sum_{k=0..n-1, gcd(k,n)=1 } * A000292(k), n>=1.
a(n) = (n*(n+2)/4!) *{n*(n+2) + mu(rad(n))*rad(n)} *phi(n)/n, n>=2, with rad(n) = A007947(n) the squarefree kernel of n, mu(n)=A008683(n), and phi(n)= A000010(n).
Note that phi(n)/n = A076512(n)/A109395(n) = phi(rad(n))/rad(n).
Proof by principle of inclusion-exclusion.

A342866 The number of elements in the continued fraction for phi(n)/n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

1, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 3, 3, 3, 4, 3, 2, 6, 3, 5, 2, 3, 3, 6, 3, 3, 3, 3, 3, 4, 3, 3, 2, 3, 3, 6, 3, 3, 2, 5, 3, 6, 3, 3, 4, 3, 3, 4, 2, 7, 4, 3, 3, 6, 4, 3, 2, 3, 3, 4, 3, 6, 3, 3, 3, 3, 3, 3, 3, 4, 3, 6

Offset: 1

Amiram Eldar, Mar 27 2021

			a(2) = 2 since the continued fraction of phi(2)/2 = 1/2 = 0 + 1/2 has 2 elements: {0, 2}.
a(3) = 3 since the continued fraction of phi(3)/3 = 2/3 = 0 + 1/(1 + 1/2) has 3 elements: {0, 1, 2}.
a(15) = 4 since the continued fraction of phi(15)/15 = 8/15 = 0 + 1/(1 + 1/(1 + 1/7)) has 4 elements: {0, 1, 1, 7}.

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

Cf. A000010, A007694, A076512, A109395, A342867.

Cf. A071862 (similar, with sigma(n)/n).

a[n_] := Length @ ContinuedFraction[EulerPhi[n]/n]; Array[a, 100]

a(n) = #contfrac(eulerphi(n)/n); \\ Michel Marcus, Mar 30 2021

a(n) = 2 if and only if n is in A007694.

a(p) = 3 for an odd prime p.

A373318 Numerator of the asymptotic density of numbers that are unitarily divided by n.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 3, 8, 1, 16, 1, 18, 1, 4, 5, 22, 1, 4, 3, 2, 3, 28, 2, 30, 1, 20, 4, 24, 1, 36, 9, 8, 1, 40, 1, 42, 5, 8, 11, 46, 1, 6, 1, 32, 3, 52, 1, 8, 3, 4, 7, 58, 1, 60, 15, 4, 1, 48, 5, 66, 2, 44, 6, 70, 1, 72, 9, 8, 9, 60, 2, 78

Offset: 1

Amiram Eldar, Jun 01 2024

Numbers that are unitarily divided by n are numbers k such that n is a unitary divisor of k, or equivalently, numbers of the form m*n, with gcd(m, n) = 1.

			Fractions begin with: 1, 1/4, 2/9, 1/8, 4/25, 1/18, 6/49, 1/16, 2/27, 1/25, 10/121, 1/36, ...
For n = 2, the numbers that are unitarily divided by 2 are the numbers of the form 4*k+2 whose asymptotic density is 1/4. Therefore a(2) = numerator(1/4) = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Unitary Divisor.
Wikipedia, Unitary divisor.

Cf. A000010, A003277, A034444, A064549, A076512, A077610, A109395, A173557, A373319(denominators), A373320.
Cf. A001620, A013661, A306016.
Numbers that are unitarily divided by k: A000027 (k=1), A016825 (k=2), A016051 (k=3), A017113 (k=4), A051062 (k=8), A051063 (k=9).

a[n_] := Numerator[EulerPhi[n]/n^2]; Array[a, 100]

PARI
```
a(n) = numerator(eulerphi(n)/n^2);
```

a(n) = 1 if and only if n is in A090778.
a(n) = A000010(n) if and only if n is a cyclic number (A003277).
Let f(n) = a(n)/A373319(n). Then:
f(n) = A000010(n)/n^2 = A076512(n)/(n*A109395(n)).
f(n) = A173557(n)/A064549(n).
f(n) is multiplicative with f(p^e) = (1 - 1/p)/p^e.
Sum_{k=1..n} f(k) = (log(n) + gamma - zeta'(2)/zeta(2)) / zeta(2), where gamma is Euler's constant (A001620).

A353347 Numbers k such that the elements of the continued fraction of phi(k)/k and phi(k+1)/(k+1) are anagrams of each other.

Original entry on oeis.org

1287, 96074, 5600160, 18486908, 41746312, 78700687, 211818591, 346666215, 535185325, 600248114, 617086359, 682116194, 972901517, 1326113558, 1397946770, 1404159416, 1785588903, 2090593128, 2286664100, 2349999964, 2396173329, 3154287487, 4029358361, 5401346573

Offset: 1

Amiram Eldar, Apr 15 2022

nonn

			1287 is a term since the sequences of elements of the continued fractions of phi(1287)/1287 = 80/143 and phi(1288)/1288 = 66/161, {0, 1, 1, 3, 1, 2, 2, 2} and {0, 2, 2, 3, 1, 1, 1, 2} respectively, are anagrams of each other.

Cf. A000010 (phi), A069567, A076512, A109395, A342866, A353345, A353346.

r[n_] := Sort[ContinuedFraction[EulerPhi[n]/n]]; seq[max_] := Module[{s = {}, n = 2, c = 0, r1 = r[1], r2}, While[n < max, r2 = r[n]; If[r1 == r2, AppendTo[s, n - 1]]; r1 = r2; n++]; s]; seq[6*10^6]

A073540 Composite numbers k such that k/phi(k) - sigma(k)/k has numerator equal to 1.

Original entry on oeis.org

4, 6, 8, 9, 16, 24, 25, 27, 28, 32, 40, 49, 64, 81, 121, 125, 128, 169, 224, 243, 256, 289, 343, 360, 361, 496, 512, 529, 625, 672, 729, 841, 864, 936, 961, 1024, 1331, 1369, 1681, 1849, 2016, 2048, 2176, 2187, 2197, 2209, 2401, 2809, 3125, 3481, 3721, 4096

Offset: 1

Benoit Cloitre, Aug 27 2002

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

Cf. A000010, A000203, A017665, A017666, A076512, A109395.

Select[Range[4100], ! PrimeQ[#] && Numerator[#/EulerPhi[#] - DivisorSigma[1, #]/#] == 1 &] (* Jayanta Basu, Jul 01 2013 *)

isok(k) = if (!isprime(k), numerator(k/eulerphi(k) - sigma(k)/k) == 1); \\ Michel Marcus, May 10 2022

A192330 Minimum number of endpoints of a tree so that there exists a zero-entropy map defined on it having a period n orbit.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 6, 5, 11, 3, 13, 7, 10, 2, 17, 6, 19, 5, 14, 11, 23, 3, 20, 13, 15, 7, 29, 10, 31, 2, 22, 17, 28, 6, 37, 19, 26, 5, 41, 14, 43, 11, 25, 23, 47, 3, 42, 20, 34, 13, 53, 15, 44, 7, 38, 29, 59, 10, 61, 31, 35, 2, 52, 22, 67, 17, 46, 28, 71, 6, 73, 37

Offset: 1

David Juher, Jun 28 2011

nonn

The topological entropy of a continuous map from a compact metric space into itself is a quantitative measure of the complexity of the dynamical system defined by the iteration of the map. See Adler, Konheim, McAndrew reference.

			a(2^n)=2 for n > 0, a(p)=p for p prime, a(k*2^j) = a(k) for k > 0, j >= 0.

Klaus Brockhaus, Table of n, a(n) for n = 1..10000
R. L. Adler, A. G. Konheim and M. H. McAndrew, Topological entropy, Trans. Amer. Math. Soc. 114 (1965), 309-319.
E. Barrabés, D. Juher, The minimum tree for a given zero entropy period, Int. J. Math. Math. Sci. 2005:19 (2005), pp. 3025-3033.

Cf. A006948 (zero-entropy permutations of length n), A109395 (denominator of phi(n)/n, phi(n)=A000010(n) is the Euler totient function).

A192330:=func< n | n-s where s:=w eq [] select 0 else &+w where w:=[ &*[ v[i]: i in [k..#v] ]: k in [2..#v] ] where v:=&cat[ [ f[j, 1]: i in [1..f[j, 2]] ]: j in [1..#f] ] where f:=Factorization(n) >; [ A192330(n): n in [1..75] ]; // Klaus Brockhaus, Jul 02 2011

A192330(n)=
{local(f=factor(n), v=[], k, s); for(j=1, #f[, 2], for(i=1, f[j, 2], v=concat(v, f[j, 1]))); k=#v; s=sum(i=2, k, prod(j=i, k, v[j])); n-s}
vector(75, n, A192330(n)) \\ Klaus Brockhaus, Jul 02 2011

a(n) = n - Sum_{i=2..k} Product_{j=i..k} s_j, where n = s_1*s_2*...*s_k with s_i primes and s_i <= s_{i+1}.

A260141 Numerators of the distinct common values of sigma(n)/n and m/phi(m) in the order which they occur when n and m increase.

Original entry on oeis.org

1, 3, 2, 7, 15, 7, 5, 13, 3, 65, 91, 31, 255, 31, 13, 85, 31, 35, 127, 51, 217, 1105, 403, 403, 7, 73, 221, 2555, 127, 635, 217, 527, 1651, 595, 33, 949, 133, 19, 267, 77, 511, 6851, 11, 65535, 89, 119, 665, 1397, 21845, 77, 143, 4123, 3937, 6141, 15841, 1157, 2047, 5621, 33, 1397, 15, 6141, 267

Offset: 1

Michel Marcus, Jul 17 2015

To be considered as common, a value must have appeared for some N in both sequences sigma(n)/n (A017665/A017666) and n/eulerphi(n) (A109395/A076512), with 1<=n<=N.

			sigma(n)/n starts: 1/1, 3/2, 4/3, 7/4, 6/5, 2/1, 8/7, 15/8, 13/9, 9/5, ...
m/phi(m) starts:   1/1, 2/1, 3/2, 2/1, 5/4, 3/1, 7/6,  2/1,  3/2, 5/2, ...
The 1st common value is 1/1 = sigma(1)/1 = 1/eulerphi(1).
The 2nd common value is 3/2 = 3/eulerphi(3) = sigma(2)/2.
The 3rd common value is 2/1 = sigma(6)/6 = 2/eulerphi(2).
The sequence of ratios begin: 1, 3/2, 2, 7/3, 15/8, 7/4, 5/2, 13/6, 3, 65/24, 91/36, 31/10, 255/128, 31/12, ...
So this sequence begins 1, 3, 2, ...

Cf. A259850, A260142 (denominators).

already(vsv, val, vsi, n) = {pos=vecsearch(vsv, val); if (pos, until(vsv[pos] < val, pos--); pos++; pos = vsi[pos] <= n); pos;}
lista(nn) = {vrat = [1]; vsrat = [1]; ve = vector(nn, k, k/eulerphi(k)); vs = vector(nn, k, sigma(k)/k); vesv = vecsort(ve); vesi = vecsort(ve,,1); vssv = vecsort(vs); vssi = vecsort(vs,,1); print1(1, ", "); for (n=2, nn, rn = vs[n]; if (!vecsearch(vsrat, rn) && (already(vesv, rn, vesi, n)), print1(numerator(rn), ", "); vrat = concat(vrat, rn); vsrat = vecsort(vrat,,8), rn = ve[n]; if (!vecsearch(vsrat, rn) && (already(vssv, rn, vssi, n)), print1(numerator(rn), ", "); vrat = concat(vrat, rn); vsrat = vecsort(vrat,,8););););}

cp's OEIS Frontend

A259850 Numbers k such that k/phi(k) equals sigma(x)/x for some x<=k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Extensions

A295314 a(n) = sigma(n) / gcd(sigma(n), phi(sigma(n))).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A127415 a(n) = Sum_{1<=k<=n, gcd(k,n)=1}, A000217(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A189918 Sum of tetrahedral numbers A000292(k), with k in the reduced residue system modulo n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A342866 The number of elements in the continued fraction for phi(n)/n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A373318 Numerator of the asymptotic density of numbers that are unitarily divided by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A353347 Numbers k such that the elements of the continued fraction of phi(k)/k and phi(k+1)/(k+1) are anagrams of each other.

Views

Author

Keywords

Examples

Crossrefs