A235353 -id:A235353 - cp's OEIS frontend

A033950 Refactorable numbers: number of divisors of k divides k. Also known as tau numbers.

1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, 84, 88, 96, 104, 108, 128, 132, 136, 152, 156, 180, 184, 204, 225, 228, 232, 240, 248, 252, 276, 288, 296, 328, 344, 348, 360, 372, 376, 384, 396, 424, 441, 444, 448, 450, 468, 472, 480, 488, 492, 504, 516, 536

Offset: 1

Simon Colton (simonco(AT)cs.york.ac.uk)

Kennedy and Cooper show that this sequence has density zero.
Spiro showed more precisely that the number of refactorable numbers less than x is asymptotic to (x/sqrt(log x))(log(log x))^(-1+o(1)). - David Eppstein, Aug 25 2014
Numbers k such that the equation gcd(k,x) = tau(k) has solutions. - Benoit Cloitre, Jun 10 2002
Refactorable numbers are the fixed points of A009230. - Labos Elemer, Nov 18 2002
Let ref(n) denote the characteristic function of the refactorable numbers. Then ref(n) = 1 + floor(n/d(n)) - ceiling(n/d(n)), where d(n) is the number of divisors of n. - Wesley Ivan Hurt, Jan 09 2013, Feb 15 2013
An odd number with an even number of divisors cannot be in the sequence by definition. Therefore all odd terms are squares (A000290). - Ivan N. Ianakiev, Aug 25 2013
A054008(k) = k mod A000005(k). - Reinhard Zumkeller, Sep 17 2014
The only squarefree terms are 1 and 2: if x is a squarefree number that is a product of n distinct primes, its number of divisors is 2^n, so x is refactorable if it contains 2^n as a factor, but that makes it nonsquarefree unless n = 0, 1, hence x = 1, 2. - Waldemar Puszkarz, Jun 10 2016
Every positive integer k occurs as tau(m) for some m in the sequence. If the factorization of k is Product p_i^e_i, then Product p_i^(p_i^e_i-1) has the specified property. For k prime, this is the only such number. - Franklin T. Adams-Watters, Jan 14 2017
Zelinsky (2002) proved that for any j > 0 and for sufficiently large m the number of terms not exceeding m is > j*pi(m), where pi(m) = A000720(m). - Amiram Eldar, Feb 20 2021
Numbers m such that the ratio (number of non-divisors of m)/(number of divisors of m) = A049820(m)/A000005(m) is an integer. - Michel Lagneau, Apr 04 2025

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B12, pp. 102-103.
New Scientist, Sep 05 1998, p. 17, para. 3.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Kushagr Ahuja, Patrick Lei and Dylan Pentland, Tau ideals in number fields, PROMYS 2017.
Alan Bundy, Simon Colton and Toby Walsh, HR - A system for Machine Discovery in Finite Algebras, ECAI 1998.
Simon Colton, Refactorable Numbers - A Machine Invention, J. Integer Sequences, Vol. 2 (1999), Article 99.1.2.
Simon Colton, HR - Automatic Theory Formation in Pure Mathematics.
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.
Claudia Spiro, How often is the number of divisors of n a divisor of n?, J. Number Theory, Vol. 21, No. 1 (1985), pp. 81-100.
Joshua Zelinsky, Tau Numbers: A Partial Proof of a Conjecture and Other Results , Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8.

Cf. A000005, A000720, A039819, A036762, A051278, A051279, A051280, A036763.
Cf. A235353 (subsequence).
Cf. A054008, A281188.

a033950 n = a033950_list !! (n-1)
a033950_list = [x | x <- [1..], x `mod` a000005 x == 0]
-- Reinhard Zumkeller, Dec 28 2011

[ n: n in [1..540] | n mod #Divisors(n) eq 0 ]; // Klaus Brockhaus, Apr 29 2009

with(numtheory):
A033950 := proc(n)
    option remember:
    local k:
    if n=1 then
        return 1:
    else
        for k from procname(n-1)+1 do
            if type(k/tau(k), integer) then
                return k:
            end if:
        end do:
    end if:
end proc:
seq(A033950(n), n=1..56); # Nathaniel Johnston, May 04 2011

Do[If[IntegerQ[n/DivisorSigma[0, n]], Print[n]], {n, 1, 1000}]
Select[ Range[559], Mod[ #, DivisorSigma[0, # ]] == 0 &]
Select[Range[550], Divisible[ #, DivisorSigma[0, # ]]&] (* Waldemar Puszkarz, Jun 10 2016 *)

isA033950(n)=n%numdiv(n)==0 \\ Charles R Greathouse IV, Jun 10 2011

from sympy import divisor_count
print([n for n in range(1, 1001) if not n % divisor_count(n)]) # Indranil Ghosh, May 03 2017

More terms from Erich Friedman

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)

A245047 Numbers n where phi(n)|n or tau(n)|n.

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 40, 48, 54, 56, 60, 64, 72, 80, 84, 88, 96, 104, 108, 128, 132, 136, 144, 152, 156, 162, 180, 184, 192, 204, 216, 225, 228, 232, 240, 248, 252, 256, 276, 288, 296, 324, 328, 344, 348, 360, 372, 376, 384, 396, 424, 432, 441, 444, 448, 450

Offset: 1

Reinhard Muehlfeld, Jul 13 2014

nonn

Phi(n) is Euler totient function (A000010); tau(n) is the number of divisors of n (A000005).

Union of A007694 and A033950. - Michel Marcus, Jul 15 2014

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A000005, A000010, A007694, A033950, A235353.

select(t -> (t mod numtheory:-phi(t) = 0) or (t mod numtheory:-tau(t) = 0), [$1..1000]); # Robert Israel, Jul 15 2014

Select[Range[500],AnyTrue[{#/EulerPhi[#],#/DivisorSigma[0,#]},IntegerQ]&] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Oct 12 2020 *)

isok(n) = !((n % eulerphi(n)) && (n % numdiv(n))); \\ Michel Marcus, Jul 15 2014

A287800 Numbers n such that phi(n) * tau(n) divides n^2, but neither tau(n) nor phi(n) divides n.

Original entry on oeis.org

900, 2400, 3840, 6480, 7200, 11520, 13056, 39168, 42240, 79200, 83232, 96000, 126720, 145200, 153600, 157440, 174240, 195840, 207360, 288000, 300000, 317520, 326592, 387840, 435600, 460800, 472320, 480000, 900000, 971520, 1056000, 1161600, 1163520, 1228800, 1440000

Offset: 1

Bernard Schott, Jun 01 2017

nonn

The GCD of the first 43 terms is 12. The GCD of the first 166 terms is 4. The GCD of a(2) through a(166) is 16. - David A. Corneth, Jun 01 2017

			For n = 900, tau(900) = 27, phi(900) = 240 and 900^2/(27 * 240) = 125, but 900/27 = 33.33333 and 900/240 = 3.75.

Amiram Eldar, Table of n, a(n) for n = 1..780 (terms below 10^10)

Cf. A000005, A000010, A007694, A033950, A235353.

[k:k in [1..1500000]| k^2 mod (EulerPhi(k) *NumberOfDivisors(k)) eq 0 and (k mod  EulerPhi(k) ne 0) and (k mod NumberOfDivisors(k) ne 0)]; // Marius A. Burtea, Dec 30 2019

for n from 1 to 100000 do p(n):=n^2/(tau(n)*phi(n));
if p(n)=floor(p(n)) and n/tau(n)<>floor(n/tau(n)) and n/phi(n)<>floor(n/phi(n)) then print(n,p(n),phi(n),tau(n)) else fi; od:

Select[Range[10^6], Function[n, And[Divisible[n^2, #1 #2], NoneTrue[{#1, #2}, Divisible[n, #] &]] & @@ {DivisorSigma[0, n], EulerPhi[n]}]] (* Michael De Vlieger, Jun 01 2017 *)

is(n) = n^2 % (numdiv(n)*eulerphi(n)) == 0 && n % numdiv(n) != 0 && n % eulerphi(n) % n!=0 \\ David A. Corneth, Jun 01 2017

A360940 Numbers k such that k / A000005(k) + k / A000010(k) is an integer.

Original entry on oeis.org

1, 2, 3, 8, 10, 12, 18, 21, 24, 28, 36, 72, 78, 96, 108, 126, 128, 168, 224, 243, 288, 294, 384, 392, 756, 864, 930, 972, 1000, 1152, 1323, 1350, 1944, 2310, 2430, 2530, 2808, 3087, 3456, 4116, 6144, 6912, 7776, 10206, 10584, 13122, 13230, 13500, 13608, 18432

Offset: 1

Ctibor O. Zizka, Feb 26 2023

nonn

It seems that odd k's {1, 3, 21, 243, 1323, 3087, ...} are relatively rare. A235353 is a subsequence of this sequence.

This sequence is infinite since A058891 is a subsequence. - Amiram Eldar, Feb 26 2023

			k = 1: 1 / A000005(1) + 1 / A000010(1) = 2, thus k = 1 is a term.
k = 2: 2 / A000005(2) + 2 / A000010(2) = 3, thus k = 2 is a term.
k = 3: 3 / A000005(3) + 3 / A000010(3) = 3, thus k = 3 is a term.
and so on.

Cf. A000005, A000010, A058891, A235353.

Select[Range[10^4], IntegerQ[#/DivisorSigma[0, #] + #/EulerPhi[#]] &] (* Amiram Eldar, Feb 26 2023 *)

from math import prod
from itertools import count, islice
from sympy import factorint
def A360940_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+t)%(s*t):
            yield k
A360940_list = list(islice(A360940_gen(),20)) # Chai Wah Wu, Mar 14 2023

cp's OEIS Frontend

A033950 Refactorable numbers: number of divisors of k divides k. Also known as tau numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Extensions

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

A245047 Numbers n where phi(n)|n or tau(n)|n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A287800 Numbers n such that phi(n) * tau(n) divides n^2, but neither tau(n) nor phi(n) divides n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A360940 Numbers k such that k / A000005(k) + k / A000010(k) is an integer.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python