A000010 -id:A000010 - cp's OEIS frontend

A365339 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nondecreasing.

1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 25, 25, 25, 25, 26, 26, 27, 27, 27

Offset: 1

Terence Tao, Sep 01 2023

a(n+1) is equal to a(n) or a(n) + 1 for every n.
It is conjectured that a(n) = pi(n) + 64 for all n >= 31957, which has been verified up to n = 10^7 (Pollack et al.), where pi is A000720. We always have a(n) >= pi(n).
Conjecture is true for n = 10^8 and n = 10^9. - Chai Wah Wu, Sep 05 2023

			a(6) = 5 because phi is nondecreasing on 1,2,3,4,5 or 1,2,3,4,6 but not on 1,2,3,4,5,6.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Thomas Bloom, Problem 49, Erdős Problems.
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M(n).
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, Ramanujan J. 30 (2013), no. 3, 379--398.
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.
Terence Tao, Erdős problem database, see no. 49.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A061070.

# Computes the first N terms of the sequence.
function A365339List(N)
    phi = [i for i in 1:N + 1]
    for i in 2:N + 1
        if phi[i] == i
            for j in i:i:N + 1
                phi[j] -= div(phi[j], i)
    end end end
    lst = zeros(Int64, N)
    dyn = zeros(Int64, N)
    for n in 1:N
        p = phi[n]
        nxt = dyn[p] + 1
        while p <= N && dyn[p] < nxt
            dyn[p] = nxt
            p += 1
        end
        lst[n] = dyn[n]
    end
    return lst
end
println(A365339List(69))  # Peter Luschny, Sep 02 2023

Table[Length[LongestOrderedSequence[Table[EulerPhi[i],{i,n}]]], {n,100}]

import math
def phi(n):
    result = n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result
# This code uses dynamic programming to print the first N=100 values of M.
N=100
M = [0 for i in range(N)]
dynamic = [0 for i in range(N+1)]
for n in range(1,N+1):
    i = phi(n)
    new = dynamic[i] + 1
    while (i<=N and dynamic[i] < new):
        dynamic[i] = new
        i+= 1
    M[n-1] = dynamic[N]
print(M)

from bisect import bisect
from sympy import totient
def A365339(n):
    plist, qlist, c = tuple(totient(i) for i in range(1,n+1)), [0]*(n+1), 0
    for i in range(n):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c # Chai Wah Wu, Sep 03 2023

Tao proves that a(n) ~ n/log n. a(n) >= pi(n) + 64 for all n >= 31957; Pollack, Pomerance, & Treviño conjecture that this is an equality. - Charles R Greathouse IV, Dec 08 2023

A366630 a(n) = phi(6^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 6, 36, 180, 1296, 6000, 41472, 230496, 1580800, 8359200, 58579200, 310968900, 2175102720, 10971642240, 76065091200, 351048600000, 2811459796992, 14508487949472, 88870766837760, 522016066337712, 3564233663616000, 17479898551382400, 128060205344805888

Offset: 0

Sean A. Irvine, Oct 14 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..430

Cf. A062394, A000010, A366623, A366618, A366627, A366628, A366629, A366670.

Cf. A053285, A366579, A366608, A366639, A366658, A366667, A366669, A366690, A366716.

EulerPhi[6^Range[0, 22] + 1] (* Paul F. Marrero Romero, Oct 17 2023 *)

PARI
```
{a(n) = eulerphi(6^n+1)}
```

a(n) = A000010(A062394(n)). - Paul F. Marrero Romero, Oct 17 2023

A366667 a(n) = phi(9^n+1), where phi is Euler's totient function (A000010).

Original entry on oeis.org

1, 4, 40, 288, 3072, 23600, 259200, 1847104, 21523360, 152845056, 1700870400, 12550120000, 130459631616, 997562438080, 11159367815680, 81159501312000, 926510094425920, 6670865700716544, 73205598106368000, 540340585126398016, 5691215305506816000

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..345

Cf. A062396, A000010, A366663, A366664, A366665, A366666.

Cf. A053285, A366579, A366608, A366618, A366630, A366639, A366658, A366669, A366690, A366716.

EulerPhi[9^Range[0, 20] + 1] (* Paul F. Marrero Romero, Nov 04 2023 *)

PARI
```
{a(n) = eulerphi(9^n+1)}
```

a(n) = A000010(A062396(n)). - Paul F. Marrero Romero, Nov 04 2023

a(n) = A366579(2*n). - Max Alekseyev, Jan 08 2024

A061468 a(n) = d(n) + phi(n), where d(n) is the number of divisors (A000005) and phi(n) is Euler's totient function (A000010).

Original entry on oeis.org

2, 3, 4, 5, 6, 6, 8, 8, 9, 8, 12, 10, 14, 10, 12, 13, 18, 12, 20, 14, 16, 14, 24, 16, 23, 16, 22, 18, 30, 16, 32, 22, 24, 20, 28, 21, 38, 22, 28, 24, 42, 20, 44, 26, 30, 26, 48, 26, 45, 26, 36, 30, 54, 26, 44, 32, 40, 32, 60, 28, 62, 34, 42, 39, 52, 28

Offset: 1

Amarnath Murthy, May 04 2001

If d(n) increases phi(n) tends to go down so the sum has a significance.

			a(20) = d(20) + phi(20) = 6 + 8 = 14.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A000005, A000010.

with(numtheory); A061468 := n-> tau(n) + phi(n);

Table[DivisorSigma[0,n]+EulerPhi[n],{n,70}] (* Harvey P. Dale, Aug 22 2020 *)

{ for (n=1, 1000, write("b061468.txt", n, " ", numdiv(n) + eulerphi(n)) ) } \\ Harry J. Smith, Jul 23 2009

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), May 19 2001

A176472 Smallest m for which A064380(m) - A000010(m) = n.

Original entry on oeis.org

2, 4, 9, 12, 22, 18, 38, 16, 93, 45, 62, 70, 44, 63, 36, 52, 64, 102, 48, 68, 84, 76, 90, 142, 146, 117, 81, 166, 174, 178, 126, 80, 150, 132, 116, 230, 124, 100, 156, 246, 266, 258, 254, 148, 112

Offset: 0

Vladimir Shevelev, Apr 18 2010

nonn

My 1981 publication studies A064380 with the quite natural convention A064380(1)=1. So a(1) could alternatively be defined as 1. By the definitions, it is clear that A064380(m) >= A000010(m).

Theorem. For every n >= 0, the equation A064380(m) - A000010(m) = n has infinitely many solutions.

V. S. Abramovich (Shevelev), On an analog of the Euler function, Proceeding of the North-Caucasus Center of the Academy of Sciences of the USSR (Rostov na Donu), 2 (1981), 13-17.
Vladimir Shevelev, Multiplicative functions in the Fermi-Dirac arithmetic, Izvestia Vuzov of the North-Caucasus region, Nature sciences 4 (1996), 28-43.

Amiram Eldar, Table of n, a(n) for n = 0..1000
Simon Litsyn and Vladimir Shevelev, On factorization of integers with restrictions on the exponent, INTEGERS: Electronic Journal of Combinatorial Number Theory, 7 (2007), #A33, 1-36.

Cf. A000010, A064380, A050376, A050292.

A176472 := proc(n) local m; for m from 2 do if A064380(m) - numtheory[phi](m) = n then return m; end if; end do: end proc: # R. J. Mathar, Jun 16 2010

infCoprimeQ[n1_, n2_] := Module[{g = GCD[n1, n2]}, If[g == 1, True, AllTrue[FactorInteger[g][[All, 1]], BitAnd @@ IntegerExponent[{n1, n2}, #] == 0&]]];
A064380[n_] := Sum[Boole[infCoprimeQ[j, n]], {j, 1, n - 1}];
a[n_] := a[n] = For[m = 2, True, m++, If[A064380[m] - EulerPhi[m] == n, Return[m]]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 05 2023, after Amiram Eldar in A064380 *)

a(2), a(3), a(8) and a(15) corrected and sequence extended by R. J. Mathar, Jun 16 2010

A176509 Composite numbers m for which A064380(m) = A000010(m).

Original entry on oeis.org

8, 27, 125, 128, 343, 1331, 2187, 2197, 4913, 6859, 12167, 24389, 29791, 32768, 50653, 68921, 78125, 79507, 103823, 148877, 205379, 226981, 300763, 357911, 389017, 493039, 571787, 704969, 823543, 912673, 1030301, 1092727, 1225043, 1295029, 1442897, 2048383, 2248091

Offset: 1

Vladimir Shevelev, Apr 19 2010

nonn

Theorem. A064380(m) = A000010(m) iff m has the form m=p^(2^k-1), k>=1, p a prime. Eliminating the primes (k=1), the terms of the sequence have this form for k>1. All terms of A030078 (k=2) and A092759 (k=3) and prime powers of A010803 (k=4) are in the sequence, for example.

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

Cf. A000010, A010803, A030078, A050376, A056824, A064380, A092759, A176472.

seq[max_] := Module[{ps = Select[Range[Floor[Surd[max, 3]]], PrimeQ], e, k, s = {}}, Do[e = Floor[Log[ps[[i]], max]]; k = Floor[Log2[e + 1]]; s = Join[s, ps[[i]]^(2^Range[2, k] - 1)], {i, 1, Length[ps]}]; Sort[s]]; seq[3*10^6] (* Amiram Eldar, Mar 26 2023 *)

is(n)=my(e=isprimepower(n));e>2 && 2^valuation(e+1,2)==e+1 \\ Charles R Greathouse IV, Feb 19 2013

a(n) ~ n^3 log^3 n. - Charles R Greathouse IV, Feb 19 2013

Sum_{n>=1} 1/a(n) = Sum_{k>=2} 1/P(2^k-1) = 0.183077059924063305405..., where P(s) is the prime zeta function. - Amiram Eldar, Jul 11 2024

128 inserted, 1024 deleted, 2187 inserted, 32768 inserted, etc. - R. J. Mathar, Nov 21 2010

More terms from Amiram Eldar, Mar 26 2023

A179187 Numbers n such that phi(n)=phi(n+5), with Euler's totient function phi=A000010.

Original entry on oeis.org

5, 9, 15, 21, 15556, 21016, 25930, 25935, 27027, 36304, 46683, 129675, 266128, 307923, 329175, 430348, 503139, 636400, 684411, 812170, 1014778, 1252713, 1777545, 1871788, 1892452, 1911987, 2622160, 2629930, 2731360, 2947035, 3397480, 4200100, 5451537

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

There are only 43 terms below 10^7, and 1843 terms below 10^12. [Jud McCranie, Feb 13 2012]

Jud McCranie, Table of n, a(n) for n = 1..1843 (terms < 10^12)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A007015.

[n: n in [1..5000000] | EulerPhi(n) eq EulerPhi(n+5)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[5000000], EulerPhi[#] == EulerPhi[# + 5] &] (* Vincenzo Librandi, Sep 08 2016 *)
Position[Partition[EulerPhi[Range[55*10^5]],6,1],?(#[[1]] == #[[6]]&), {1}, Heads->False]//Flatten (* _Harvey P. Dale, Nov 10 2016 *)

{op=vector(N=5); for( n=1,1e7,if( op[n%N+1]+0==op[n%N+1]=eulerphi(n),print1(n-N,",")))}

A000010(a(n)) = A000010(a(n)+5).

A242960 Numbers n such that 7^A000010(n) == 1 (mod n^2).

Original entry on oeis.org

4, 5, 10, 20, 40, 80, 491531, 983062, 1966124, 2457655, 3932248, 4915310, 6389903, 9339089, 9830620, 12288275, 12779806, 18678178, 19169709, 19661240, 24576550, 25559612, 28017267, 31949515, 37356356, 38339418, 39322480, 46695445, 49153100, 51119224, 56034534

Offset: 1

Felix Fröhlich, May 27 2014

nonn

Giovanni Resta, Table of n, a(n) for n = 1..425

Cf. A077816, A242959, A000010. All primes in this sequence are in A123693.

for(n=2, 10^9, if(Mod(7, n^2)^(eulerphi(n))==1, print1(n, ", ")))

Terms a(23) and beyond from Giovanni Resta, Jan 24 2020

A262311 Number of ordered ways to write n = x^2 + y^2 + phi(z^2) (0 <= x <= y and z > 0) with y or z prime, where phi(.) is Euler's totient function given by A000010.

Original entry on oeis.org

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

Offset: 1

Zhi-Wei Sun, Oct 01 2015

nonn

Conjecture: a(n) > 0 for all n > 1.
I have verified this for n up to 10^6, and found that a(n) = 1 for the following 67 values of n: 2, 3, 4, 5, 8, 9, 13, 23, 29, 32, 39, 48, 68, 96, 108, 140, 144, 215, 264, 268, 324, 328, 384, 396, 404, 460, 471, 476, 500, 503, 684, 716, 759, 764, 768, 788, 860, 908, 936, 1032, 1076, 1112, 1148, 1164, 1259, 1344, 1399, 1443, 1484, 1503, 1551, 1839, 1868, 2088, 2723, 2883, 3744, 4296, 5963, 6804, 8328, 9680, 10331, 11948, 21524, 39716, 94415. It seems that a(n) = 1 for no other values of n.
It is easy to see that all the numbers phi(n^2) = n*phi(n) (n = 1,2,3,...) are pairwise distinct.
See also A262781 for a similar conjecture.

			a(2) = 1 since 2 = 0^2 + 0^2 + phi(2^2) with 2 prime.
a(5) = 1 since 5 = 0^2 + 2^2 + phi(1^2) with 2 prime.
a(23) = 1 since 23 = 1^2 + 4^2 + phi(3^2) with 3 prime.
a(29) = 1 since 29 = 0^2 + 3^2 + phi(5^2) with 3 and 5 both prime.
a(48) = 1 since 48 = 2^2 + 2^2 + phi(10^2) with 2 prime.
a(96) = 1 since 96 = 3^2 + 9^2 + phi(3^2) with 3 prime.
a(140) = 1 since 140 = 7^2 + 7^2 + phi(7^2) with 7 prime.
a(471) = 1 since 471 = 0^2 + 19^2 + phi(11^2) with 19 and 11 both prime.
a(476) = 1 since 476 = 8^2 + 16^2 + phi(13^2) with 13 prime.
a(936) = 1 since 936 = 4^2 + 30^2 + phi(5^2) with 5 prime.
a(1112) = 1 since 1112 = 23^2 + 23^2 + phi(9^2) with 23 prime.
a(1839) = 1 since 1839 = 3^2 + 30^2 + phi(31^2) with 31 prime.
a(1868) = 1 since 1868 = 2^2 + 2^2 + phi(62^2) with 2 prime.
a(2088) = 1 since 2088 = 15^2 + 39^2 + phi(19^2) with 19 prime.
a(2723) = 1 since 2723 = 34^2 + 35^2 + phi(19^2) with 19 prime.
a(2883) = 1 since 2883 = 21^2 + 44^2 + phi(23^2) with 23 prime.
a(3744) = 1 since 3744 = 4^2 + 54^2 + phi(29^2) with 29 prime.
a(4296) = 1 since 4296 = 26^2 + 60^2 + phi(5^2) with 5 prime.
a(5963) = 1 since 5963 = 26^2 + 59^2 + phi(43^2) with 59 and 43 both prime.
a(6804) = 1 since 6804 = 40^2 + 72^2 + phi(5^2) with 5 prime.
a(8328) = 1 since 8328 = 1^2 + 39^2 + phi(83^2) with 83 prime.
a(9680) = 1 since 9680 = 68^2 + 70^2 + phi(13^2) with 13 prime.
a(10331) = 1 since 10331 = 17^2 + 100^2 + phi(7^2) with 7 prime.
a(11948) = 1 since 11948 = 5^2 + 109^2 + phi(7^2) with 109 and 7 both prime.
a(21524) = 1 since 21524 = 59^2 + 109^2 + phi(79^2) with 109 and 79 both prime.
a(39716) = 1 since 39716 = 5^2 + 17^2 + phi(199^2) with 17 and 199 both prime.
a(94415) = 1 since 94415 = 115^2 + 178^2 + phi(223^2) with 223 prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A000290, A001481, A002618, A262747, A262781.

SQ[n_]:=IntegerQ[Sqrt[n]]
f[n_]:=EulerPhi[n^2]
Do[r=0;Do[If[f[z]>n,Goto[aa]];Do[If[SQ[n-f[z]-x^2]&&(PrimeQ[z]||PrimeQ[Sqrt[n-f[z]-x^2]]),r=r+1],{x,0,Sqrt[(n-f[z])/2]}];Label[aa];Continue,{z,1,n}];Print[n," ",r];Continue,{n,1,100}]

A286610 Restricted growth sequence computed for Euler totient function phi, A000010.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 3, 4, 3, 5, 3, 6, 4, 7, 7, 8, 4, 9, 7, 6, 5, 10, 7, 11, 6, 9, 6, 12, 7, 13, 8, 11, 8, 14, 6, 15, 9, 14, 8, 16, 6, 17, 11, 14, 10, 18, 8, 17, 11, 19, 14, 20, 9, 16, 14, 15, 12, 21, 8, 22, 13, 15, 19, 23, 11, 24, 19, 25, 14, 26, 14, 27, 15, 16, 15, 22, 14, 28, 19, 29, 16, 30, 14, 31, 17, 32, 16, 33, 14, 27, 25, 22, 18, 27, 19, 34, 17, 22

Offset: 1

Antti Karttunen, May 11 2017

nonn

			Construction: we start with a(1)=1 for phi(1)=1 (where phi = A000010), and then after, for all n > 1, whenever the value of phi(n) has not been encountered before, we set a(n) to the least natural number k not already in sequence among a(1) .. a(n-1), otherwise [whenever phi(n) = phi(m), for some m < n], we set a(n) = a(m), i.e., to the same value that was assigned to a(m).
For n=2, phi(2) = 1, which value was already encountered as phi(1), thus we set also a(2) = 1.
For n=3, phi(3) = 2, which has not been encountered before, thus we allot for a(3) the least so far unused number, which is 2, thus a(3) = 2.
For n=4, phi(4) = 2, which was already encountered as at n=3 for the first time, thus we set a(4) = a(3) = 2.
For n=5, phi(5) = 4, which has not been encountered before, thus we allot for a(5) the least so far unused number, which is now 3, thus a(5) = 3.

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

Cf. A000010, A210719 (positions of records, and also the first occurrence of each n).

Cf. also A101296, A286603, A286605, A286619, A286621, A286622, A286626, A286378 for similarly constructed sequences.

With[{nn = 99}, Function[s, Table[Position[Keys@ s, k_ /; MemberQ[k, n]][[1, 1]], {n, nn}]]@ Map[#1 -> #2 & @@ # &, Transpose@ {Values@ #, Keys@ #}] &@ PositionIndex@ Array[EulerPhi, nn]] (* Michael De Vlieger, May 12 2017, Version 10 *)

rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences,invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A000010(n) = eulerphi(n);
write_to_bfile(1,rgs_transform(vector(10000,n,A000010(n))),"b286610.txt");

cp's OEIS Frontend

A365339 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nondecreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Mathematica

Python

Python

Formula

A366630 a(n) = phi(6^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A366667 a(n) = phi(9^n+1), where phi is Euler's totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A061468 a(n) = d(n) + phi(n), where d(n) is the number of divisors (A000005) and phi(n) is Euler's totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A176472 Smallest m for which A064380(m) - A000010(m) = n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A176509 Composite numbers m for which A064380(m) = A000010(m).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A179187 Numbers n such that phi(n)=phi(n+5), with Euler's totient function phi=A000010.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs