A007694 -id:A007694 - cp's OEIS frontend

A055458 a(n) = smallest composite solution x to the equation phi(x+2n) = phi(x)+2n.

6, 12, 21, 24, 36, 45, 48, 39, 63, 72, 72, 95, 60, 57, 224, 84, 15, 135, 1058, 45, 301, 144

Offset: 1

Labos Elemer, Jun 26 2000

Sivaramakrishnan (1989) quotes Makowski, who gave solutions for phi(x+d) = phi(x)+d with d = 2^a and d = 2*3^a. Compare also A007694 and A049237.
Smallest prime solutions appear to be identical with A054906.
a(23) is presently unknown.
The sequence continues as (with ? for unknown values): ?, 95, 162, 63, 189, 69, 156, 161, 180, 69, 260, 150, ?, 115, 204, 129, 400, 75, 180, 165, 35, 117, 476, 7105, 288, 195, ?, 324, 620, 240, 81, 145, 14531, 153, 644, 309, ?, 203, ?, 63, 640, 75, 372, 285, 2312, 33, 343, 642, 336, 155, ?, 147, 728, 396, 1564, 185, 564, 87, 567, 360, 360, 155, 492, 510, 560, 516, 516, 301, 4232, 261, 860, 387, 576, 185, 564, 309, 1000, 225 ... - Don Reble, Apr 29 2015

			a(19) = 1058 because phi(1058 + 38) = phi(1096) = 544 = 506 + 38 = phi(1058) + 38.
a(100) = 225, phi(225 + 200) = phi(425) = 320 = 120 + 200 = phi(225) + 200.

Sivaramakrishnan, R. (1989): Classical theory of Arithmetical Functions. Marcel Dekker, Inc., New York-Basel. Chapter V, Problem 20, page 113.

Cf. A000010, A054906, A050472, A050473, A007694, A049237.

A055458 := proc(n)
    local x;
    for x from 0 do
        if not isprime(x) then
        if numtheory[phi](x+2*n) = numtheory[phi](x)+2*n then
            return x;
        end if;
        end if;
    end do:
end proc: # R. J. Mathar, Sep 23 2016

Table[k = 4; While[Nand[CompositeQ@ k, EulerPhi[k + 2 n] == EulerPhi[k] + 2 n], k++]; k, {n, 22}] (* Michael De Vlieger, Dec 17 2016 *)

a(n)=forcomposite(x=4,, if(eulerphi(x+2*n) == eulerphi(x)+2*n, return(x))) \\ does not handle -1s; Charles R Greathouse IV, Apr 28 2015

More terms from Michel ten Voorde Jun 14 2003

Entry revised by N. J. A. Sloane, Apr 28 2015

A151999 Numbers k such that every prime that divides phi(k) also divides k.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 30, 32, 34, 36, 40, 42, 48, 50, 54, 60, 64, 68, 72, 78, 80, 84, 90, 96, 100, 102, 108, 110, 114, 120, 126, 128, 136, 144, 150, 156, 160, 162, 168, 170, 180, 192, 200, 204, 210, 216, 220, 222, 228, 234, 240, 250, 252, 256, 270

Offset: 1

J. Luis A. Yebra and J. Jimenez Urroz (yebra(AT)mat.upc.es), Nov 19 2008

Alternative descriptions:
(a) For every prime p|n and every prime q|p-1 we have q|n;
(b) Numbers n such that radical of phi(n) divides radical of n, where phi is Euler's totient function and radical is the squarefree kernel function.
These numbers are "valid bases".
Numbers n such that radical of phi(n) divides n. - Michel Marcus, Nov 06 2017
Pollack and Pomerance call these numbers "phi-deficient numbers". - Amiram Eldar, Jun 02 2020

Paolo P. Lava, Table of n, a(n) for n = 1..10000
Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.
J. Jimenez Urroz and J. Luis A. Yebra, On the equation a^x=x mod b^n, Journal of Integer Sequences, Vol. 12 (2009), Article 09.8.8.

Cf. A005117, A055744, A073539.
Cf. A007947 (radical of n), A007694 (phi(n) divides n, a subsequence).
Cf. A080400 (radical of phi(n)).
Cf. A152000.

[n: n in [1..300] | forall{d: d in PrimeDivisors(EulerPhi(n)) | IsIntegral(n/d)}]; // Bruno Berselli, Nov 04 2017

A151999 := proc(n)
    if n = 1 then
        2;
    else
        for a from procname(n-1)+1 do
            pdvs := numtheory[factorset](a) ;
            aworks := true;
            for p in numtheory[factorset](a) do
                for q in numtheory[factorset](p-1) do
                    if a mod q = 0 then
                        ;
                    else
                        aworks := false;
                    end if;
                end do:
            end do:
            if aworks then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Jun 01 2013

Rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[1 + Range[300], Mod[Rad[#], Rad[EulerPhi[#]]]==0 &] (* José María Grau Ribas, Jan 09 2012 *)

isok(n) = {fp = factor(n); for (i=1, #fp[, 1], fq = factor(fp[i, 1] - 1); for (j=1, #fq[, 1], if (n % fq[j, 1], return (0)););); return (1);} \\ Michel Marcus, Jun 01 2013

isok(n) = (n % factorback(factor(eulerphi(n))[, 1])) == 0; \\ Michel Marcus, Nov 04 2017

for n in range(1, 271):
    if euler_phi(n)**2 == euler_phi(euler_phi(n) * n): print(n, end=', ') # Torlach Rush, Oct 01 2024

Corrected by Michel Marcus, Jun 01 2013
Edited by N. J. A. Sloane, Jun 02 2013 at the suggestion of Michel Marcus, merging this with A204010
Deleted erroneous comment and added correct b-file by Paolo P. Lava, Nov 06 2017

A235353 Numbers m such that phi(m) and tau(m) divide m, where phi = A000010 and tau = A000005.

Original entry on oeis.org

1, 2, 8, 12, 18, 24, 36, 72, 96, 108, 128, 288, 384, 864, 972, 1152, 1944, 3456, 6144, 6912, 7776, 13122, 18432, 26244, 31104, 32768, 52488, 55296, 62208, 69984, 98304, 209952, 279936, 294912, 497664, 559872, 708588, 839808, 884736, 1679616, 3538944, 4478976

Offset: 1

Reinhard Zumkeller, Jan 06 2014

nonn

Intersection of A007694 and A033950.
From David Morales Marciel, May 01 2015: (Start)
m is always of the form (2^i)(3^j) where i>0, j>=0.
If j=0, then m is a deficient number, and sigma(m)=2m-1. The deficiency is always 1.
If j>0, then m is an abundant number. (End)

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

Cf. A000010, A000005, A007694, A003586, A033950.

a235353 n = a235353_list !! (n-1)
a235353_list = filter (\x -> mod x (a000005 x) == 0) a007694_list

Select[Range@ 1000000, And[Mod[#, EulerPhi@ #] == 0, Mod[#, DivisorSigma[0, #]] == 0] &] (* Michael De Vlieger, May 05 2015 *)
Select[Range[55*10^5],Mod[#,EulerPhi[#]]==Mod[#,DivisorSigma[0,#]]==0&] (* Harvey P. Dale, Feb 22 2023 *)

for(n=1,10^6,if(!(n%numdiv(n)+n%eulerphi(n)),print1(n,", "))) \\ Derek Orr, Apr 30 2015

sm3(n)=if(n<1, 0, n>>=valuation(n,2); 3^valuation(n,3)==n)
list(lim)=my(v=List([1]),t); for(i=1,log(lim)\log(2), if(!sm3(i+1), next); for(j=0,log(lim>>i)\log(3), t=2^i*3^j; if(t%((i+1)*(j+1))==0, listput(v,t)))); Set(v) \\ Charles R Greathouse IV, May 05 2015

from itertools import count, islice
from math import prod
from sympy import factorint
def A235353_gen(startvalue=1): # generator of terms >= startvalue
    for k in count(max(startvalue,1)):
        f = factorint(k)
        t = prod(p**(e-1)*(p-1) for p, e in f.items())
        s = prod(e+1 for e in f.values())
        if not (k%s or k%t):
            yield k
A235353_list = list(islice(A235353_gen(),20)) # Chai Wah Wu, Mar 14 2023

A068997 Numbers k such that Sum_{d|k} d*mu(d) divides k.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 48, 54, 64, 72, 80, 84, 96, 100, 108, 120, 128, 144, 160, 162, 168, 192, 200, 216, 240, 252, 256, 272, 288, 312, 320, 324, 336, 360, 384, 400, 432, 440, 480, 486, 500, 504, 512, 544, 576, 588, 600, 624, 640, 648

Offset: 1

Benoit Cloitre, Apr 07 2002

Numbers k such that A023900(k) divides k.
The only squarefree terms so far are a(1), a(2), and a(4). - Torlach Rush, Dec 04 2017
There are no more squarefree terms. The squarefree terms are also the squarefree terms of A007694 since A023900(n) = A008683(n) * A000010(n) for squarefree numbers n, and A007694 contains only 3-smooth numbers (A003586). - Amiram Eldar, Apr 19 2025
There is a surjective mapping from all even numbers not in this sequence to terms of the sequence. The first such is 10 to a(9). The next is 14, 28, 42 to a(19). All even numbers not in the sequence are divisors of some term in the sequence. - Torlach Rush, Dec 08 2017

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A000010, A003586, A007694, A008683, A023900, A173557, A293928.

a068997 n = a068997_list !! (n - 1)
a068997_list = filter (\x -> mod x (a173557 x) == 0) [1..]
-- Reinhard Zumkeller, Jun 01 2015

with(numtheory): A068997 := i->`if`(i mod phi(mul(j,j=factorset(i)))=0,i,NULL): seq(A068997(i),i=1..650); # Peter Luschny, Nov 02 2010

Select[Range[650], Divisible[#, DivisorSum[#, # MoebiusMu[#] &]] &] (* Michael De Vlieger, Nov 20 2017 *)
q[1] =True; q[n_] := Divisible[n, Times @@ ((First[#] - 1) & /@ FactorInteger[n])]; Select[Range[650], q] (* Amiram Eldar, Apr 19 2025 *)

for(n=1,1000,if(n%sumdiv(n,d,moebius(d)*d)==0,print1(n,",")))

isok(k) = !(k % vecprod(apply(x -> 1-x, factor(k)[, 1]))); \\ Amiram Eldar, Apr 19 2025

A062356 a(n) = floor(n/phi(n)).

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 2

Offset: 1

Jason Earls, Jul 07 2001

Reference does not include the floor function.

See A007694 for the numbers for which n/phi(n) is an integer, and A049237 for the ratios.

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc. Boston MA, 1976, Prob. 7-4 3, p. 152.

Harry J. Smith, Table of n, a(n) for n=1,...,2000

Cf. A000010, A007694, A049237.

Table[Floor[n/EulerPhi@ n], {n, 120}] (* Michael De Vlieger, Jul 02 2016 *)

(a(n)=n\eulerphi(n)); vector(250,n,a(n)) \\ Edited by M. F. Hasler, Jul 02 2016

{ for (n=1, 2000, write("b062356.txt", n, " ", floor(n/eulerphi(n))) ) } \\ Harry J. Smith, Aug 05 2009; irrelevant realprecision(...) deleted by M. F. Hasler, Jul 02 2016

From M. F. Hasler, Jul 02 2016: (Start)
A062356(n = 2k+1) = 1 except for n in A036798.
A062356(n = 6k+2) = 2 except for n in 70*{11, 17, 23, 26, 29, 38, 44, 62, 65, 68, 77, 92, 95, 104, 110, ...} or n in 10*{2717, 4199, 4301, 4433, 4862, 5291, 5423, 6149, 6578, 7106, 8294, 8723, 9581, 9614, ...} or n = 646646, 874874, ....
A062356(n = 6k+4) = 2 except for n in 70*{13, 19, 22, 31, 34, 46, 52, 55, 58, 76, 85, 88, 91, 115, 121, ...} or n in 10*{2431, 3289, 3553, 4147, 4807, 5083, 5434, 5797, 5863, 6061, 6721, 6919, 7579, 8398, 8437, 8602, 8866, 9724, ...} or n = 782782, 986986, ....
A062356(n = 6k) = 3 except for n in 30*{7, 11, 13, 14, 21, 22, 26, 28, 33, 35, 39, 42, 44, 49, 52, 55, 56, 63, 65, 66, 70, 77, 78, 84, 88, 91, 98, 99, ...} or n in 42*{143, 187, 209, 221, 247, 253, 286, 374, 418, 429, 442, 494, 506, 561, 572, 627, 663, 741, 748, 759, 836, 858, 884,...} or n = 277134, 554268, 831402, .... (End)

A187778 Numbers k dividing psi(k), where psi is the Dedekind psi function (A001615).

Original entry on oeis.org

1, 6, 12, 18, 24, 36, 48, 54, 72, 96, 108, 144, 162, 192, 216, 288, 324, 384, 432, 486, 576, 648, 768, 864, 972, 1152, 1296, 1458, 1536, 1728, 1944, 2304, 2592, 2916, 3072, 3456, 3888, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8748, 9216, 10368, 11664, 12288, 13122, 13824, 15552, 17496, 18432, 20736, 23328

Offset: 1

Enrique Pérez Herrero, Jan 05 2013

nonn

This sequence is closed under multiplication.
Also 1 and the numbers where psi(n)/n = 2, or n/phi(n)=3, or psi(n)/phi(n)=6.
Also 1 and the numbers of the form 2^i*3^j with i, j >= 1 (A033845).
If M(n) is the n X n matrix whose elements m(i,j) = 2^i*3^j, with i, j >= 1, then det(M(n))=0.
Numbers n such that Product_{i=1..q} (1 + 1/d(i)) is an integer where q is the number of the distinct prime divisors d(i) of n. - Michel Lagneau, Jun 17 2016

			psi(48) = 96 and 96/48 = 2 so 48 is in this sequence.

S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..191 from Vincenzo Librandi)
R. Blecksmith, M. McCallum and J. L. Selfridge, 3-smooth representations of integers, Amer. Math. Monthly, 105 (1998), 529-543.
E. Deutsch, Tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
Eric Weisstein's World of Mathematics, Smooth Number
Wikipedia, Closure

Cf. A003586, A001615, A007694, A033950, A074946, A075592.

[6*n: n in [1..3000] | PrimeDivisors(n) subset [2, 3]]; // Vincenzo Librandi, Jan 11 2019

Select[Range[10^4],#/EulerPhi[#]==3 || #==1&]
Join[{1}, 6 Select[Range@4000, Last@Map[First, FactorInteger@#]<=3 &]] (* Vincenzo Librandi, Jan 11 2019 *)

dedekindpsi(n) = if( n<1, 0, direuler( p=2, n, (1 + X) / (1 - p*X)) [n]);
k=0; n=0; while(k<10000,n++; if( dedekindpsi(n) % n== 0, k++; print1(n, ", ")));

For n > 1, a(n) = 6 * A003586(n).

Sum_{n>0} 1/a(n)^k = 1 + Sum_{i>0} Sum_{j>0} 1/(2^i * 3^j)^k = 1 + 1/((2^k-1)*(3^k-1)).

A215486 n - 1 mod phi(n), where phi(n) is Euler's totient function.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 3, 0, 1, 6, 7, 0, 5, 0, 3, 8, 1, 0, 7, 4, 1, 8, 3, 0, 5, 0, 15, 12, 1, 10, 11, 0, 1, 14, 7, 0, 5, 0, 3, 20, 1, 0, 15, 6, 9, 18, 3, 0, 17, 14, 7, 20, 1, 0, 11, 0, 1, 26, 31, 16, 5, 0, 3, 24, 21, 0, 23, 0, 1, 34, 3, 16, 5, 0, 15, 26, 1, 0, 11, 20, 1, 30, 7, 0, 17

Offset: 1

Alonso del Arte, Feb 17 2013, based on an idea from Balarka Sen

Lehmer conjectured that a(n) = 0 only when n is 1 or prime.

			a(8) = 3 because 8 - 1 mod phi(8) = 3.
a(9) = 2 because 9 - 1 mod phi(9) = 2.
a(10) = 1 because 10 - 1 mod phi(10) = 1.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Wikipedia, Lehmer's totient problem

Cf. A068494, A007694.

[(n-1) mod EulerPhi(n): n in [2..90]]; // Bruno Berselli, Feb 18 2013

Table[Mod[n - 1, EulerPhi[n]], {n, 2, 100}]

makelist(mod(n-1,totient(n)), n, 2, 90); /* Bruno Berselli, Feb 18 2013 */

a(n)=(n-1)%eulerphi(n) \\ Charles R Greathouse IV, Dec 29 2013

A336066 Numbers k such that the exponent of the highest power of 2 dividing k (A007814) is a divisor of k.

Original entry on oeis.org

2, 4, 6, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 34, 36, 38, 42, 44, 46, 48, 50, 52, 54, 58, 60, 62, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 90, 92, 94, 98, 100, 102, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 130, 132, 134, 138, 140, 142, 144

Offset: 1

Amiram Eldar, Jul 07 2020

nonn

All the terms are even by definition.
If m is a term then m*(2*k+1) is a term for all k>=1.
Šalát (1994) proved that the asymptotic density of this sequence is 0.435611... (A336067).

			2 is a term since A007814(2) = 1 is a divisor of 2.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Tibor Šalát, On the function a_p, p^a_p(n) || n (n > 1), Mathematica Slovaca, Vol. 44, No. 2 (1994), pp. 143-151.

A001146 and A039956 are subsequences.
Cf. A007814, A336067.
Similar sequences: A033950, A005349, A006446, A074946, A075592, A007694, A112249, A336068.

Select[Range[2, 150, 2], Divisible[#, IntegerExponent[#, 2]] &]

isok(m) = if (!(m%2), (m % valuation(m,2)) == 0); \\ Michel Marcus, Jul 08 2020

from itertools import count, islice
def A336066_gen(startvalue=2): # generator of terms >= startvalue
    return filter(lambda n:n%(~n&n-1).bit_length()==0,count(max(startvalue+startvalue&1,2),2))
A336066_list = list(islice(A336066_gen(startvalue=3),30)) # Chai Wah Wu, Jul 10 2022

A350777 Numbers k where phi(k) divides k - 3.

Original entry on oeis.org

1, 2, 3, 9, 195, 5187, 1141967133868035, 3658018932844533311864835

Offset: 1

Albert Böschow and Dennis Gruhlke, Jan 15 2022

Numbers in this sequence larger than 2 have to be odd, since phi(n) is even for n > 2, so n - 3 cannot be odd. Therefore n itself must be odd.

Terms having (k-3)/phi(k) = 2 are shared with A226105. - Max Alekseyev, Oct 26 2023

			phi(195) = 96, 195 - 3 = 192, and 96 divides 192.

Cf. A000010, A007694, A226105.

Select[Range[6000], Divisible[#-3, EulerPhi[#]] &] (* Amiram Eldar, Jan 19 2022 *)

isok(k) = !((k-3) % eulerphi(k)); \\ Michel Marcus, Jan 19 2022

from sympy import totient
print("1, 2", end=", ")
for k in range (3, 10**8, 2):
    if (k-3)%totient(k)==0:
        print(k, end=", ", flush=True) # Martin Ehrenstein, Mar 26 2022

a(7)-a(8) from Max Alekseyev, Nov 05 2023

A336068 Numbers k such that the exponent of the highest power of 3 dividing k (A007949) is a divisor of k.

Original entry on oeis.org

3, 6, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 48, 51, 54, 57, 60, 66, 69, 72, 75, 78, 84, 87, 90, 93, 96, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 156, 159, 165, 168, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204

Offset: 1

Amiram Eldar, Jul 07 2020

nonn

All the terms are divisible by 3 by definition.

Šalát (1994) proved that the asymptotic density of this sequence is 0.287106... (A336069).

			3 is a term since A007949(3) = 1 is a divisor of 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Tibor Šalát, On the function a_p, p^a_p(n) || n (n > 1), Mathematica Slovaca, Vol. 44, No. 2 (1994), pp. 143-151.

A055777 is a subsequence.
Cf. A007949, A336069.
Similar sequences: A033950, A005349, A006446, A074946, A075592, A007694, A112249, A336066.

Select[Range[200], Mod[#, 3] == 0 && Divisible[#, IntegerExponent[#, 3]] &]

isok(m) = if (!(m%3), (m % valuation(m,3)) == 0); \\ Michel Marcus, Jul 08 2020

cp's OEIS Frontend

A055458 a(n) = smallest composite solution x to the equation phi(x+2n) = phi(x)+2n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A151999 Numbers k such that every prime that divides phi(k) also divides k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Extensions

A235353 Numbers m such that phi(m) and tau(m) divide m, where phi = A000010 and tau = A000005.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A068997 Numbers k such that Sum_{d|k} d*mu(d) divides k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

A062356 a(n) = floor(n/phi(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A187778 Numbers k dividing psi(k), where psi is the Dedekind psi function (A001615).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica