A033950 -id:A033950 - cp's OEIS frontend

A111291 Number of refactorable numbers (A033950) <= 10^n.

1, 4, 16, 92, 665, 5257, 44705, 394240, 3558181, 32608999, 302172507, 2823898245

Offset: 0

Robert G. Wilson v, Nov 01 2005

Simon Colton conjectures that the number of refactorables less than x is at least x/(2 log(x)).

S. Colton, Refactorable Numbers - A Machine Invention, J. Integer Sequences, Vol. 2, 1999, #2.

c = 0; k = 1; Do[ While[k <= 10^n, If[ Mod[k, DivisorSigma[0, k]] == 0, c++ ]; k++ ]; Print[c], {n, 0, 8}]

a(9)-a(11) from Donovan Johnson, Sep 19 2009

A235990 Consider all Pythagorean triples (X,Y,Z) consisting of refactorable numbers (A033950) only, ordered by increasing Z. This sequence gives the values of Z.

Original entry on oeis.org

104, 204, 348, 480, 488, 492, 600, 732, 936, 1248, 1356, 1360, 1440, 1448, 1644, 1788, 2000, 2172, 2196, 2700, 2784, 2824, 3060, 3084, 3228, 3360, 3368, 3372, 3552, 3712, 3744, 3816, 3924, 4080, 4240, 4392, 4500, 4500, 4812, 5052, 5088, 5220, 5280, 5856, 6000

Offset: 1

Ivan N. Ianakiev, Jan 18 2014

nonn

			104^2 = 40^2 + 96^2, i.e. A033950(17)^2 = A033950(9)^2 + A033950(16)^2.

Cf. A033950, A009000, A046083, A046084.

More terms from Michel Marcus, Jan 21 2014

A343817 Refactorable numbers (A033950) which set a record for the gap to the next refactorable number.

Original entry on oeis.org

1, 2, 24, 40, 108, 156, 296, 732, 1692, 31616, 51608, 568720, 766620, 6195132, 6938752, 17879440, 18578320, 35196584, 228694176, 475292728, 589169184, 1451254356, 3252050592, 4865544096, 6328305120, 8082626976, 8694028264, 9112984448, 30328732568, 46093418640

Offset: 1

Amiram Eldar, Apr 30 2021

nonn

Since the asymptotic density of the refactorable numbers is 0 (Kennedy and Cooper, 1990), this sequence is infinite.

The corresponding record values are 1, 6, 12, 16, 20, 24, 32, 44, 92, 100, 144, 152, 180, 192, 208, 212, 236, 268, 280, 296, 336, 360, 368, 372, 384, 396, 408, 432, 488, 496, ...

			The first 8 refactorable numbers are 1, 2, 8, 9, 12, 18, 24 and 36. The gaps between them are 1, 6, 1, 3, 6, 6 and 12. The record gaps, 1, 6 and 12, occur after the refactorable numbers 1, 2 and 24, which are the first 3 terms of this sequence.

Robert E. Kennedy and Curtis N. Cooper, Tau numbers, natural density and Hardy and Wright's Theorem 437, International Journal of Mathematics and Mathematical Sciences, Vol. 13, No. 2 (1990), pp. 383-386.

Cf. A033950, A114617.

refQ[n_] := Divisible[n, DivisorSigma[0, n]]; seq = {}; m = 1; dm = 0; Do[If[refQ[n], d = n - m; If[d > dm, dm = d; AppendTo[seq, m]]; m = n], {n, 2, 10^6}]; seq

A007694 Numbers k such that phi(k) divides k.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96, 108, 128, 144, 162, 192, 216, 256, 288, 324, 384, 432, 486, 512, 576, 648, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8192, 8748, 9216

Offset: 1

N. J. A. Sloane, Robert G. Wilson v

a(n) divides p^a(n) - 1 for all primes p >= 5. - Benoit Cloitre, Mar 22 2002
Also k such that Sum_{d divides k} mu(d)/d has numerator 1. - Benoit Cloitre, Apr 15 2002
k is here if and only if phi(k) also divides cototient(k). On the other hand, cototient(k) divides phi(k) if and only if k is a prime or power of a prime. - Labos Elemer, May 03 2002
It follows that k/phi(k) = 2 if k is a power of 2 and equal to 3 if k is of the form 6*A003586. - Gary Detlefs, Jun 28 2011
1 and even 3-smooth numbers, cf. A003586. - Reinhard Zumkeller, Jan 06 2014
Numbers k such that k = (1+omega(k))*phi(k). - Farideh Firoozbakht, Oct 02 2014
These are the integers whose largest squarefree divisor is 1, 2 or 6. As such, this sequence is equal to the set V_infinite, defined as the intersection of the V_k for k >= 1, where V_k(x) = {phi_k(n) <= x} and phi_k is the k-th iterate of phi, the Euler function; for instance, V_1 is given by A002202 (see Theorem 7 in Pomerance and Luca). - Michel Marcus, Nov 09 2015
This sequence is contained in A068997. The terms of A068997 not in this sequence have largest squarefree divisor other than 1, 2, or 6, beginning with 10. - Torlach Rush, Dec 07 2017

			12 is in the sequence because 12/phi(12) = 12/4 = 3, which is an integer.
16 is in the sequence because 16/phi(16) = 16/8 = 2, which is an integer.
20 is not in the sequence because 20/phi(20) = 20/8 = 5/2 = 2.5, which is not an integer.

J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique Des Nombres, Problem 526 pp. 71; 256, Ellipses Paris 2004.
Sárközy A. and Suranyi J., Number Theory Problem Book (in Hungarian), Tankonyvkiado, Budapest, 1972.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
Roohollah Ebrahimian, When Does phi(n) divide n? A Number Theory Math Competition Problem., YouTube video, 2023.
Michael W. Ecker and Scott J. Beslin, Problem E3037, Amer. Math. Monthly, Vol. 93, No. 8 (1986), pp. 656-657.
Florian Luca and Carl Pomerance, On the range of the iterated Euler function, Article 8, Integers: Electronic Journal of Combinatorial Number Theory, Proceedings of the Integers Conference 2007, Volume 9 Supplement (2009).
Mathematics Stack Exchange, Is there phi(n)/n = 6
Wacław Sierpiński, Elementary Theory of Numbers, Warszawa, 1964.

Cf. A000010, A049237, A007694, A007947, A003557, A023200, A003586, A001221, A033950, A235353 (subsequence), A068997 (subsequence).

a007694 n = a007694_list !! (n-1)
a007694_list = 1 : filter even a003586_list
-- Reinhard Zumkeller, Jan 06 2014

select(n -> n mod numtheory:-phi(n) = 0, [$1..5000]); # Robert Israel, Nov 03 2014

Select[ Range[5000], IntegerQ[ #/EulerPhi[ # ]] &]
m = 5000; Join[{1}, Sort @ Flatten @ Table[2^i*3^j, {i, 1, Log2[m]}, {j, 0, Log[3, m/2^i]}]] (* Amiram Eldar, Oct 29 2020 *)

for(n=1,10^6, if (n%eulerphi(n)==0,print1(n,", "))); \\ Joerg Arndt, Apr 04 2013

list(lim)=my(v=List([1]),t); for(i=1,logint(lim\1,2), listput(v,t=2^i); for(j=1,logint(lim\t,3), listput(v,t*=3))); Set(v) \\ Charles R Greathouse IV, Nov 10 2015

library(numbers); j=N=1
while(j<200) if(isNatural((N=N+1)/eulersPhi(N))) dtot[(j=j+1)]=N # Christian N. K. Anderson, Apr 04 2013

is_A007694 = lambda n: euler_phi(n).divides(n)
A007694_list = lambda len: filter(is_A007694, (1..len))
A007694_list(4100) # Peter Luschny, Oct 03 2014

k/phi(k) is an integer if and only if k = 1 or k = 2^w * 3^u for w > 0 and u >= 0.
k/phi(k) = 3 if and only if phi(k)|k and 3|k. - Thomas Ordowski, Nov 03 2014
a(n) is approximately exp(sqrt(2*log(2)*log(3)*n))/sqrt(3/2). - Charles R Greathouse IV, Nov 10 2015
From Amiram Eldar, Oct 29 2020: (Start)
a(n) = 2 * A003586(n) for n > 1.
Sum_{n>=1} 1/a(n) = 5/2. (End)

A034884 Numbers k such that k < d(k)^2, where d(k) = A000005(k).

Original entry on oeis.org

2, 3, 4, 6, 8, 10, 12, 14, 15, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 72, 80, 84, 90, 96, 108, 120, 126, 132, 140, 144, 168, 180, 192, 210, 216, 240, 252, 288, 300, 336, 360, 420, 480, 504, 540, 720, 840, 1260

Offset: 1

Erich Friedman

See comment in A175495. - Vladimir Shevelev, May 07 2013
The deficient terms are 2, 3, 4, 8, 10, 14, 15, 16, 32; the first perfect or abundant number not listed is 66 = 2 * 3 * 11; the only term not 7-smooth is 132 = 2^2 * 3 * 11; the largest not divisible by 6 is 140 = 2^2 * 5 * 7. - Peter Munn, Sep 19 2021
The union of this sequence and A276734 has 74 total terms which are all k with floor(sqrt(k)) <= d(k). - Bill McEachen, Apr 07 2023

Cf. A000005, A035033, A035034, A035035, A033950, A036763, A175495, A276734.

Select[Range[1300],#Harvey P. Dale, Apr 11 2014 *)

isok(n) = (n < numdiv(n)^2) \\ Michel Marcus, Jun 07 2013

Labos Elemer added the last three terms and observes that this sequence is now complete.

A141586 Strongly refactorable numbers: numbers n such that if n is divisible by d, it is divisible by the number of divisors of d.

Original entry on oeis.org

1, 2, 12, 24, 36, 72, 240, 480, 720, 1440, 3360, 4320, 5280, 6240, 6720, 8160, 9120, 10080, 11040, 13440, 13920, 14880, 15840, 17760, 18720, 19680, 20160, 20640, 21600, 22560, 24480, 25440, 27360, 28320, 29280, 32160, 33120, 34080

Offset: 1

J. Lowell, Aug 19 2008

nonn

Let n = Product_{p} p ^ e_p be the prime factorization of n and let M = max{e_p + 1 }. Then n is in the sequence iff for all primes q in the range 2 <= q <= M we have e_q >= Sum_{r} floor( log_q (e_r + 1) ). - N. J. A. Sloane, Sep 01 2008
All terms > 1 are even. A subsequence of A033950. - N. J. A. Sloane, Aug 27 2008
Contains 480*p for all primes p > 5 (see A109802). - N. J. A. Sloane, Aug 27 2008

			72 qualifies because its divisors are 1,2,3,4,6,8,9,12,18,24,36,72, which have 1,2,2,3,4,4,3,6,6,8,9,12 divisors respectively and all of those numbers are divisors of 72.

Dmitriy Kunisky, German Manoim and N. J. A. Sloane, On strongly refactorable numbers, in preparation.

German Manoim and N. J. A. Sloane, Sep 09 2008, Table of n, a(n) for n = 1..240937 [a large file]

Cf. A033950, A134865, A109802, A141551, A141756, A141758, A141900, A142593, A142594, A100549, A100762, A082725, A135130, A143718, A143719, A143720.

isA141586 := proc(n) local dvs,d ; dvs := numtheory[divisors](n) ; for d in dvs do if not numtheory[tau](d) in dvs then RETURN(false) : fi; od: RETURN(true) ; end: for n from 1 to 100000 do if isA141586(n) then printf("%d,",n) ; fi; od: # R. J. Mathar, Aug 26 2008
## A100549: if n = prod_p p^e_p, then pp = largest prime <= 1 + max e_p
with(numtheory):
pp := proc(n) local f,m; option remember; if (n = 1) then return 1; end if; m := 1: for f in op(2..-1,ifactors(n)) do if (f[2] > m) then m := f[2]: end if; end do; prevprime(m+2); end proc;
isA141586 := proc(n) local ff,f,g,p,i; global pp;
ff := op(2..-1,ifactors(n));
for f in ff do
p := f[1];
if (add(floor(log(1+g[2])/log(p)),g in ff) > f[2]) then
return false;
end if;
end do;
for i from 1 to pi(pp(n)) do
p := ithprime(i);
if (n mod p <> 0) then
if (add(floor(log(1+g[2])/log(p)),g in ff) > 0) then
return false;
end if;
end if;
end do;
return true;
end proc; # David Applegate and N. J. A. Sloane, Sep 15 2008

l = {}; For[n = 1, n < 100000, n++, b = DivisorSigma[0, Divisors[n]]; If[Length[Select[b, Mod[n, # ] > 0 &]] == 0, AppendTo[l, n]]]; l (* Stefan Steinerberger, Aug 25 2008 *)
sfnQ[n_]:=AllTrue[DivisorSigma[0,Divisors[n]],Mod[n,#]==0&]; Select[ Range[ 35000],sfnQ] (* The program uses the AllTrue function from Mathematica version 10 *) (* Harvey P. Dale, Jan 27 2019 *)

is_A141586(n)={ bittest(n,0) & return(n==1); fordiv(n,d,n % numdiv(d) & return);1 } \\ M. F. Hasler, Dec 05 2010

is_A141586 = lambda n: all(number_of_divisors(d).divides(n) for d in divisors(n)) # D. S. McNeil, Dec 05 2010

More terms from German Manoim (gerrymanoim(AT)gmail.com), Aug 27 2008

A035033 Numbers k such that k <= d(k)^2, where d() = number of divisors (A000005).

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 72, 80, 84, 90, 96, 108, 120, 126, 132, 140, 144, 168, 180, 192, 210, 216, 240, 252, 288, 300, 336, 360, 420, 480, 504, 540, 720, 840, 1260

Offset: 1

Erich Friedman, Labos Elemer

Cf. A000005, A035034, A035035, A033950, A036763, A034884, A273323.

Select[Range[1300],#<=DivisorSigma[0,#]^2&] (* Harvey P. Dale, Mar 16 2012 *)

is(n)=numdiv(n)^2>=n \\ Charles R Greathouse IV, Aug 03 2012

A036763 Numbers k such that k*d(x) = x has no solution for x, where d (A000005) is the number of divisors; sequence gives impossible x/d(x) quotients in order of magnitude.

Original entry on oeis.org

18, 27, 30, 45, 63, 64, 72, 99, 105, 112, 117, 144, 153, 160, 162, 165, 171, 195, 207, 225, 243, 252, 255, 261, 279, 285, 288, 294, 320, 333, 336, 345, 352, 360, 369, 387, 396, 405, 416, 423, 435, 441, 465, 468, 477, 490, 504, 531, 544, 549, 555, 567, 576

Offset: 1

Labos Elemer

nonn

A special case of a bound on d(n) by Erdős and Suranyi (1960) was used to get a limit: a = x/d(x) > 0.5*sqrt(x) and below 4194304 a computer test shows these values did not occur as x = a*d(x). For larger x this is impossible since if d(x) < sqrt(x), then x/d(x) > sqrt(4194304) = 2048 > the given terms.
A051521(a(n)) = 0. - Reinhard Zumkeller, Dec 28 2011
This sequence contains all numbers of the form k = 9p, p prime (i.e., k = 18, 27, 45, 63, 99, ...). - Jianing Song, Nov 25 2018

			No natural number x exists for which x = 18*d(x), so 18 is a term.

P. Erdős and J. Suranyi, Selected Topics in Number Theory, Tankonyvkiado, Budapest, 1960 (in Hungarian).
P. Erdős and J. Suranyi, Selected Topics in Number Theory, Springer, New York, 2003 (in English).

Donovan Johnson, Table of n, a(n) for n = 1..5000

Cf. A000005, A033950, A036761, A036762, A036764, A051278, A051279, A051280, A051521.

a036763 n = a036763_list !! (n-1)
a036763_list = filter ((== 0) . a051521) [1..]
-- Reinhard Zumkeller, Dec 28 2011

with(numtheory): A036763 := proc(n) local k,p: for k from 1 to 4*n^2 do p:=n*k: if(p=n*tau(p))then return NULL: fi: od: return n: end: seq(A036763(n),n=1..100); # Nathaniel Johnston, May 04 2011

noSolQ[n_] := !AnyTrue[Range[4*n^2], # == DivisorSigma[0, n*#]& ];
Reap[Do[If[noSolQ[n], Print[n]; Sow[n]], {n, 600}]][[2, 1]] (* Jean-François Alcover, Jan 30 2018 *)

Definition corrected by N. J. A. Sloane, May 18 2022 at the suggestion of David James Sycamore.

A034797 a(0) = 0; a(n+1) = a(n) + 2^a(n).

Original entry on oeis.org

0, 1, 3, 11, 2059

Offset: 0

Joseph Shipman (shipman(AT)savera.com)

First impartial game with value n, using natural enumeration of impartial games.
The natural 1-1 correspondence between nonnegative numbers and hereditarily finite sets is given by f(A)=sum over members m of A of 2^f(m). A set can be considered an impartial game where the legal moves are the members. The value of an impartial game is always an ordinal (for finite games, an integer).
The next term, a(5) = 2^2059 + 2059, has 620 decimal digits and is too large to include. - Olivier Gérard, Jun 26 2001
Positions of records in A103318. - N. J. A. Sloane and David Applegate, Mar 21 2005
The first n terms in this sequence form the lexicographically earliest n-vertex clique in the Ackermann-Rado encoding of the Rado graph (an infinite graph in which vertex i is adjacent to vertex j, with iDavid Eppstein, Aug 22 2014
This sequence was used by Spiro to bound the density of refactorable numbers (A033950). - David Eppstein, Aug 22 2014
For any positive integer m, a(1), a(2), ..., a(3^m) modulo 3^m form a complete residue set. - Yifan Xie, Aug 19 2025

J. H. Conway, On Numbers and Games, Academic Press.

N. J. A. Sloane, Table of n, a(n) for n = 0..5
Wilhelm Ackermann, Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Math. Ann. 114 (1939), no. 1, 305-315.
David Applegate, Benoit Cloitre, Philippe Deléham and N. J. A. Sloane, Sloping binary numbers: a new sequence related to the binary numbers, J. Integer Seq. 8 (2005), no. 3, Article 05.3.6, 15 pp. Preprint versions: [pdf, ps].
O. Kurganskyy and I. Potapov, Reachability problems for PAMs, arXiv preprint arXiv:1510.04121 [cs.NA], 2015.
Richard Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340.
Claudia Spiro, How often is the number of divisors of n a divisor of n?, J. Number Theory 21 (1985), no. 1, 81-100.
Wikipedia, Rado graph.

Cf. A034798, A103318.

a=0;lst={a};Do[AppendTo[lst,a+=2^a],{n,0,4}];lst (* Vladimir Joseph Stephan Orlovsky, May 06 2010 *)
NestList[#+2^#&,0,5] (* Harvey P. Dale, Mar 22 2020 *)

A114617 Numbers k such that k and k+1 are both refactorable numbers.

Original entry on oeis.org

1, 8, 1520, 50624, 62000, 103040, 199808, 221840, 269360, 463760, 690560, 848240, 986048, 1252160, 1418480, 2169728, 2692880, 2792240, 3448448, 3721040, 3932288, 5574320, 5716880, 6066368, 6890624, 6922160, 8485568

Offset: 1

Eric W. Weisstein, Dec 16 2005

nonn

It is not possible to have three consecutive refactorable numbers (see the link). The sequence is best viewed in base 12, with X for 10 and E for 11: 1, 8, X68, 25368, 2EX68, 4E768, 97768, X8468, 10EX68, 1X4468, 293768, 34XX68, 3E6768, 504768, 584X68, 887768, X9X468, E27X68, 11X3768, 12E5468, 1397768, 1X49X68, 1XE8468, 2046768, 2383768, 2399X68, 2X12768. After the first two terms all terms are 68, 368, 468, 668, 768, X68 mod 1000 (base 12). - Walter Kehowski, Jun 19 2006
No successive refactorables seem to be of the form odd, odd+1. If such a pair exist, they must be very large. The first pair of successive refactorables not divisible by 3 is (5*19)^4-1, (5*19)^4. - Walter Kehowski, Jun 25 2006
Zelinsky (2002, Theorem 59, p. 15) proved that all the terms above 1 are even. - Amiram Eldar, Feb 20 2021

Jud McCranie, Table of n, a(n) for n = 1..94342 First 1000 terms by Donovan Johnson.
Joshua Zelinsky, Tau Numbers: A Partial Proof of a Conjecture and Other Results, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8.
Eric Weisstein's World of Mathematics, Refactorable Number.

Cf. A033950, A036898.

Filtered([1..10^6],n->n mod Tau(n)=0 and (n+1) mod Tau(n+1)=0 ); # Muniru A Asiru, Dec 21 2018

with(numtheory); RFC:=[]: for w to 1 do for k from 1 to 12^6 do n:=144*k+(6*12+8); if andmap(z-> z mod tau(z) = 0,[n,n+1]) then RFC:=[op(RFC),n]; print(n); fi od od; # it is possible to remove the condition n = (6*12+8) mod 12^2 but you'll get the same sequence. - Walter Kehowski, Jun 19 2006

Select[Join[{1, 8}, 144*Range[10^5] + 80], Mod[#, DivisorSigma[0, #]] == 0 && Mod[#+1, DivisorSigma[0, #+1]] == 0 & ](* Jean-François Alcover, Oct 25 2012, after Walter Kehowski *)

isok(n) = !(n % numdiv(n)) && !((n+1) % numdiv(n+1)); \\ Michel Marcus, Dec 21 2018

a(n) mod tau(a(n)) = 0 and (a(n)+1) mod tau(a(n)+1) = 0 where tau(n) is the number of divisors of n. - Walter Kehowski, Jun 19 2006

cp's OEIS Frontend

A111291 Number of refactorable numbers (A033950) <= 10^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A235990 Consider all Pythagorean triples (X,Y,Z) consisting of refactorable numbers (A033950) only, ordered by increasing Z. This sequence gives the values of Z.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A343817 Refactorable numbers (A033950) which set a record for the gap to the next refactorable number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A007694 Numbers k such that phi(k) divides k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

R

Sage

Formula

A034884 Numbers k such that k < d(k)^2, where d(k) = A000005(k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A141586 Strongly refactorable numbers: numbers n such that if n is divisible by d, it is divisible by the number of divisors of d.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Extensions

A035033 Numbers k such that k <= d(k)^2, where d() = number of divisors (A000005).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

A036763 Numbers k such that k*d(x) = x has no solution for x, where d (A000005) is the number of divisors; sequence gives impossible x/d(x) quotients in order of magnitude.