A055744 -id:A055744 - cp's OEIS frontend

A256248 Indices of powers of two in A055744 (the sequence of n that have the same prime power set as phi(n)).

1, 2, 3, 4, 6, 10, 14, 20, 29, 41, 57, 79, 110, 153, 210, 286, 392, 534, 723, 982, 1330, 1790, 2415, 3249, 4359, 5838, 7824, 10457, 13949, 18581, 24724, 32848, 43568, 57723, 76429, 101095, 133599, 176414, 232772, 306920, 404256, 532034, 699655, 919551, 1207627

Offset: 1

Michel Marcus, Mar 20 2015

nonn

All powers of 2, including 1, but excluding 2 itself (A151821) are terms of A055744.
This sequence lists the positions of A151821 terms within A055744.
Is a(n+1)/a(n) ~ 4/3 for large n? - David A. Corneth, Mar 21 2015
A209229(A055744(a(n))) = 1. - Reinhard Zumkeller, Jun 01 2015

			The first terms of A055744 are 1, 4, 8, 16, 18, 32, among which 18 is the only integer that is not a power of 2. Thus this sequence starts with 1, 2, 3, 4, 6.

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..50
Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.

Cf. A055744, A151821.

Cf. A209229.

a256248 n = a256248_list !! (n-1)
a256248_list = filter ((== 1) . a209229 . a055744) [1..]
-- Reinhard Zumkeller, Jun 01 2015

t = Select[Range@ 1000000, First /@ FactorInteger@# == First /@ FactorInteger@ EulerPhi@ # &]; f[n_] := Block[{pf = FactorInteger@ n, p2}, p2 = First@ First@ pf; If[Length@ pf == 1 && First@ First@ pf == 2, Last@ First@ pf, 0]]; {1}~Join~Flatten@ Position[f /@ t, n_ /; n > 0] (* Michael De Vlieger, Mar 21 2015 *)

lista(nn) = {nb = 0; for (n=1, nn, if (factor(n)[, 1]==factor(eulerphi(n))[, 1], nb++; if (n == 2^valuation(n, 2), print1(nb, ", "));););}

a(30)-a(45) from Hiroaki Yamanouchi, Mar 31 2015

A256430 The least positive integer in A055744 divisible by A008578(n).

Original entry on oeis.org

1, 4, 18, 50, 294, 1210, 1014, 578, 2166, 58190, 35322, 28830, 8214, 16810, 77658, 5588770, 219102, 4239858, 111630, 1481370, 1058610, 31974, 486798, 2824490, 871310, 56454, 102010, 1082118, 47330166, 71286, 536298, 677418, 6692790, 638146, 146646390, 4928622

Offset: 1

David A. Corneth, Mar 28 2015

nonn

Subset of A256431. Elements from this sequence can be used to find elements from A256431. For example, 18 and 50 are the least number in this sequence divisible by 3 and 5 respectively. These numbers can be used to find the least number in A055744 divisible by both 3 and 5 as follows: 18 = 2^1 * 3^2 and 50 = 2^1 * 5^2. 'Order' these factors together: 2^1|2^1|3^2|5^2. For two consecutive factors, if they have the same base, remove the one with the highest exponent. Leaves 2^1|3^2|5^2. Multiply these factors together. Gives 2 * 3^2 * 5^2 = 450. So 450 is in A256431. This method can be applied recursively to find the least n in A055744 divisible by 3, 5 and 7, for example; applying this to 294 and 450 gives 7350 which is the least element in A055744 divisible by primes 3, 5 and 7.

Andrew Howroyd, Table of n, a(n) for n = 1..72

With[{s = Select[Range[10^6], SameQ @@ Map[FactorInteger[#][[All, 1]] &, {#, EulerPhi@ #}] &]}, TakeWhile[#, IntegerQ] &@ Table[SelectFirst[s, Divisible[#, p] &], {p, {1}~Join~Prime@ Range@ 30}]] (* Michael De Vlieger, Feb 22 2018 *)

a(n)={my(m=0, p=if(n==1,1,prime(n-1))); until(my(f=factor(m)); f[, 1]==factor(eulerphi(f))[, 1], m+=p); m} \\ Andrew Howroyd, Mar 01 2018

a(16), a(18) and other terms corrected by Andrew Howroyd, Mar 01 2018

A256431 Numbers A055744(n) such that for any k < n, A055744(k) and A055744(n) do not have all their prime factors in common.

Original entry on oeis.org

1, 4, 18, 50, 294, 450, 578, 1014, 1210, 2166, 5202, 7350, 8214, 10890, 14450, 16810, 25350, 28830, 31974, 35322, 49686, 54150, 56454, 58190, 71286, 77658, 84966, 102010, 106134, 111630, 130050, 132098, 151290, 159414, 177870, 205350, 219102, 223494, 293046, 349690, 366054, 402486, 486798, 523710, 536298, 613470

Offset: 1

David A. Corneth, Mar 28 2015

nonn

Subsequence of A055744.
These numbers can be used to find terms from A055744. For instance, 294 = 2 * 3 * 7^2, so for all a, b, c >= 0, all numbers of the form 294 * 2^a * 3^b * 7^c are in A055744.
No two terms in this sequence can be used to find the same term from A055744 with this method, as every term in this sequence has a different set of distinct prime factors. This is because any two numbers that do not have the same set of distinct prime factors are different, by the fundamental theorem of arithmetic.
Also, a complete list of terms of this sequence up to n enables the computation of all terms of A055744 up to at least n.
The squarefree kernel (or radical, see A007947) of the terms of this sequence is different from the radical of all lesser terms of A055744. - Michel Marcus, Aug 06 2015

			a(3) = 18 is in A055744 and it is the smallest number in A055744 having prime factors 2 and 3.
a(6) = 450 is in A055744 and it is divisible by a(3) = 18 and by a(4) = 50 but it is the smallest element in A055744 having prime factors 2, 3 and 5.

David A. Corneth, Table of n, a(n) for n = 1..2553 (all < 10^11)

Cf. A007947, A055744, A256430.

isA055744(n)=my(f=factor(n)); f[,1]==factor(eulerphi(f))[,1]
is(n)=my(f=factor(n),r=factorback(f[,1])); for(i=1,#f~,f[i,2]--); sumdiv(f,d,isA055744(d*r))==1 \\ Charles R Greathouse IV, May 26 2015

A141718 Duplicate of A055744.

Original entry on oeis.org

1, 4, 8, 16, 18, 32, 36, 50, 54, 64, 72, 100, 108, 128, 144, 162, 200, 216, 250, 256, 288, 294, 324, 400, 432, 450, 486, 500, 512, 576, 578, 588, 648, 800, 864, 882, 900, 972, 1000, 1014, 1024, 1152, 1156, 1176, 1210, 1250, 1296, 1350, 1458, 1600, 1728, 1764

Offset: 1

dead

A151821 Powers of 2, omitting 2 itself.

Original entry on oeis.org

1, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592

Offset: 1

N. J. A. Sloane, Jul 08 2009

Different from A046055.
An elephant sequence, see A175655. For the central square just one A[5] vector, with decimal value 170, leads to this sequence. For the corner squares this vector leads to the companion sequence A095121. - Johannes W. Meijer, Aug 15 2010
This is a subsequence of A055744, numbers n such that n and phi(n) have same prime factors. - Michel Marcus, Mar 20 2015
INVERTi transform of A007483: (1, 5, 17, 61, 217, 773, ...). - Gary W. Adamson, Aug 06 2016
Nonprimes that are also powers of 2. Intersection of A000079 and A018252. - Omar E. Pol, Jan 27 2017
Also the chromatic number of the n-Keller graph. - Eric W. Weisstein, Nov 17 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Eric Weisstein's World of Mathematics, Chromatic Number
Eric Weisstein's World of Mathematics, Keller Graph
Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A000079, A007483, A018252, A020707, A046055, A055744, A063759, A095121, A175655.

Partial sums are given by 2*A000225(n)-1, which is not the same as A000918.

a151821 n = a151821_list !! (n-1)
a151821_list = x : xs where (x : _ : xs) = a000079_list
-- Reinhard Zumkeller, Dec 16 2013

[1] cat [2^n: n in [2..35]]; // Vincenzo Librandi, Jul 21 2013

CoefficientList[Series[(1 + 2 x)/(1 - 2 x), {x, 0, 40}], x] (* Vincenzo Librandi, Jul 21 2013 *)
DeleteCases[2^Range[0, 33], p_ /; PrimeQ @ p] (* Michael De Vlieger, Aug 06 2016 *)
Join[{1}, 2^Range[2, 20]] (* Eric W. Weisstein, Nov 17 2017 *)

a(n)=if(n>1,2^n,1) \\ Charles R Greathouse IV, Dec 08 2015

Vec(x*(1+2*x)/(1-2*x) + O(x^100)) \\ Altug Alkan, Dec 09 2015

def A151821(n): return 1<1 else 1 # Chai Wah Wu, Jun 10 2025

G.f.: x*(1+2*x)/(1-2*x). - Philippe Deléham, Sep 17 2009
a(1) = 1 and a(n) = 3 + Sum_{k=1..n-1} a(k) for n>=2. - Joerg Arndt, Aug 15 2012
E.g.f.: exp(2*x) - x - 1. - Stefano Spezia, Jan 31 2023

A027598 Numbers k such that the set of prime divisors of k is equal to the set of prime divisors of sigma(k).

Original entry on oeis.org

1, 6, 28, 120, 270, 496, 672, 1080, 1638, 1782, 3780, 8128, 18600, 20580, 24948, 26208, 30240, 32640, 32760, 35640, 41850, 44226, 55860, 66960, 164640, 167400, 185220, 199584, 273000, 293760, 401310, 441936, 446880, 502740, 523776, 614250, 707616, 802620, 819000

Offset: 1

Jud McCranie

nonn

Multiplicities are ignored.
All even perfect numbers are in the sequence. It seems that 1 is the only odd term of the sequence. - Farideh Firoozbakht, Jul 01 2008
sigma() is the multiplicative sum-of-divisors function. - Walter Nissen, Dec 16 2009
Pollack and Pomerance call these "prime-perfect numbers" and show that there are << x^(1/3+e) of these up to x for any e > 0. - Charles R Greathouse IV, May 09 2013
Except for unity for the obvious reason, the primitive terms are the perfect numbers (A000396). - Robert G. Wilson v, Feb 19 2019
If an odd term > 1 exists, it is larger than 5*10^23. - Giovanni Resta, Jun 02 2020

			273000 = 2^3*3*5^3*7*13 and sigma(273000) = 1048320 = 2^8*3^2*5*7*13 so 273000 is in the sequence.

R. K. Guy, Unsolved Problems in Number Theory, B19.

Donovan Johnson, Table of n, a(n) for n = 1..500 (first 100 terms from T. D. Noe)
Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.

Intersection of A105402 and A175200. - Amiram Eldar, Jun 02 2020

Cf. A110751, A110819, A055744, A081377, A000203.

Filtered([1..1000000],n->Set(Factors(n))=Set(Factors(Sigma(n)))); # Muniru A Asiru, Feb 21 2019

Select[Range[1000000], Transpose[FactorInteger[#]][[1]] == Transpose[FactorInteger[DivisorSigma[1, #]]][[1]] &] (* T. D. Noe, Dec 08 2012 *)

a(n) = {for (i=1, n, fn = factor(i); fs = factor(sigma(i)); if (fn[,1] == fs[,1], print1(i, ", ")););} \\ Michel Marcus, Nov 18 2012

is(n)=my(f=factor(n),fs=[],t);for(i=1,#f[,1], t=factor((f[i,1]^(f[i,2]+1)-1)/(f[i,1]-1))[,1]; fs=vecsort(concat(fs,t~),,8); if(#setminus(fs,f[,1]~), return(0))); fs==f[,1]~ \\ Charles R Greathouse IV, May 09 2013

Edited by N. J. A. Sloane, Jul 12 2008 at the suggestion of R. J. Mathar

A081377 Numbers n such that the set of prime divisors of phi(n) is equal to the set of prime divisors of sigma(n).

Original entry on oeis.org

1, 3, 14, 35, 42, 70, 105, 119, 209, 210, 238, 248, 297, 357, 418, 477, 594, 595, 616, 627, 714, 744, 954, 1045, 1178, 1190, 1240, 1254, 1463, 1485, 1672, 1674, 1736, 1785, 1848, 1863, 2079, 2090, 2376, 2385, 2540, 2728, 2926, 2945, 2970, 3080, 3135, 3302

Offset: 1

Labos Elemer, Mar 26 2003

nonn

The multiplicities of the divisors are to be ignored.

Is it true that 1 is the only term in both this sequence and A055744? - Farideh Firoozbakht, Jul 01 2008. Answer from Luke Pebody, Jul 10 2008: No! In fact the numbers 103654150315463023813006470 and 6534150553412193640795377701190 are in both sequences.

			n=418=2*11*19: sigma(418)=720, phi[418]=180, common prime factor set ={2,3,5}
k = 477 = 3*3*53: sigma(477) = 702 = 2*3*3*3*13; phi(477) = 312 = 2*2*2*3*13; common factor set: {2,3,13}.
phi(89999)=66528=2^5*3^3*7*11 and sigma(89999)=118272=2^9*3*7*11 so 89999 is in the sequence.

T. D. Noe, Table of n, a(n) for n = 1..1000
Prime Puzzles, Puzzle 451

Cf. A000010, A000203, A076533, A065642, A081378, A110751, A110819, A027598, A141718.

ffi[x_] := Flatten[FactorInteger[x]] lf[x_] := Length[FactorInteger[x]] ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}] Do[s=ba[DivisorSigma[1, n]]; s1=ba[EulerPhi[n]]; If[Equal[s, s1], k=k+1; Print[n]], {n, 1, 10000}]

is(n)=factor(eulerphi(n=factor(n)))[,1]==factor(sigma(n))[,1] \\ Charles R Greathouse IV, Nov 27 2013

Edited by N. J. A. Sloane, Jul 11 2008 at the suggestion of Farideh Firoozbakht

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

A073539 Numbers k such that if p is a prime dividing k then p divides phi(k).

Original entry on oeis.org

1, 4, 8, 9, 16, 18, 25, 27, 32, 36, 49, 50, 54, 64, 72, 81, 98, 100, 108, 121, 125, 128, 144, 147, 162, 169, 196, 200, 216, 225, 242, 243, 250, 256, 288, 289, 294, 324, 338, 343, 361, 392, 400, 432, 441, 450, 484, 486, 500, 507, 512, 529, 576, 578, 588, 605

Offset: 1

Benoit Cloitre, Aug 27 2002

Converse does not necessarily hold: phi(k) may have prime factors not dividing k.
Numbers k for which phi(k)*lambda(k) == 0 (mod k), where lambda(k) = A002322(k) is the Carmichael function. - Michel Lagneau, Nov 18 2012
Pollack and Pomerance call these numbers "phi-abundant numbers". Numbers k such that rad(k) | phi(k), where rad(k) is the squarefree kernel of k (A007947). - Amiram Eldar, Jun 02 2020
If p is the largest prime divisor of a term k, then p^2 divides k. - Max Alekseyev, Aug 27 2024

			98 = 2*7^2 and phi(98)=2*3*7 so if p divides 98 then p divides phi(98), hence 98 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harvey P. Dale)
Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.

Cf. A090779, A000010, A002322, A007947, A055744, A151999, A280936.

[n: n in [1..620] | IsZero(EulerPhi(n)^NumberOfDivisors(n) mod n)]; // Bruno Berselli, Jul 27 2012

Select[Range[700],And@@Divisible[EulerPhi[#],Transpose[FactorInteger[#]] [[1]]]&] (* Harvey P. Dale, Nov 02 2011 *)

A211413 Numbers m such that phi(m) is a power of the product of the distinct prime factors of m.

Original entry on oeis.org

1, 4, 8, 16, 18, 32, 64, 108, 128, 250, 256, 512, 648, 1024, 2048, 2500, 3888, 4096, 6174, 8192, 16384, 23328, 25000, 32768, 41154, 65536, 101250, 131072, 139968, 250000, 259308, 262144, 524288, 839808, 1048576, 1542294, 2097152, 2500000, 2839714

Offset: 1

Giovanni Resta, Feb 10 2013

nonn

Sequence contains the numbers 2^(k+1), 2^k*3^(k+1) and 25*10^k, for k > 0.

a(226) > 10^18.

			m = 178726991395974 = 2*3*7^2*883^4 and phi(m) = 2^3*3^3*7^3*883^3.

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

Cf. A105261.

Subsequence of A055744.

Select[Range[10^5], # == 1 || IntegerQ @ Log[Times @@ First /@ FactorInteger @ #, EulerPhi @ #] &]

cp's OEIS Frontend

A256248 Indices of powers of two in A055744 (the sequence of n that have the same prime power set as phi(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A256430 The least positive integer in A055744 divisible by A008578(n).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Extensions

A256431 Numbers A055744(n) such that for any k < n, A055744(k) and A055744(n) do not have all their prime factors in common.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A141718 Duplicate of A055744.

Views

Author

Keywords

A151821 Powers of 2, omitting 2 itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Python

Formula

A027598 Numbers k such that the set of prime divisors of k is equal to the set of prime divisors of sigma(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

PARI

PARI

Extensions

A081377 Numbers n such that the set of prime divisors of phi(n) is equal to the set of prime divisors of sigma(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions