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

%I #156 Oct 20 2024 21:52:14

%S 1,2,8,9,12,18,24,36,40,56,60,72,80,84,88,96,104,108,128,132,136,152,

%T 156,180,184,204,225,228,232,240,248,252,276,288,296,328,344,348,360,

%U 372,376,384,396,424,441,444,448,450,468,472,480,488,492,504,516,536

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

%C Kennedy and Cooper show that this sequence has density zero.

%C 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

%C Numbers k such that the equation gcd(k,x) = tau(k) has solutions. - _Benoit Cloitre_, Jun 10 2002

%C Refactorable numbers are the fixed points of A009230. - _Labos Elemer_, Nov 18 2002

%C 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

%C 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

%C A054008(k) = k mod A000005(k). - _Reinhard Zumkeller_, Sep 17 2014

%C 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

%C 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

%C 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

%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B12, pp. 102-103.

%D New Scientist, Sep 05 1998, p. 17, para. 3.

%H Charles R Greathouse IV, <a href="/A033950/b033950.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)

%H Kushagr Ahuja, Patrick Lei and Dylan Pentland, <a href="https://www.researchgate.net/publication/329911140_TAU_IDEALS_IN_NUMBER_FIELDS">Tau ideals in number fields</a>, PROMYS 2017.

%H Alan Bundy, Simon Colton and Toby Walsh, <a href="https://core.ac.uk/download/pdf/28971036.pdf">HR - A system for Machine Discovery in Finite Algebras</a>, ECAI 1998.

%H Simon Colton, <a href="http://www.cs.uwaterloo.ca/journals/JIS/colton/joisol.html">Refactorable Numbers - A Machine Invention</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.2.

%H Simon Colton, <a href="http://www.dai.ed.ac.uk/homes/simonco/research/hr/">HR - Automatic Theory Formation in Pure Mathematics</a>.

%H Robert E. Kennedy and Curtis N. Cooper, <a href="http://dx.doi.org/10.1155/S0161171290000576">Tau numbers, natural density and Hardy and Wright's Theorem 437</a>, International Journal of Mathematics and Mathematical Sciences, Vol. 13, No. 2 (1990), pp. 383-386.

%H Claudia Spiro, <a href="http://dx.doi.org/10.1016/0022-314X(85)90012-5">How often is the number of divisors of n a divisor of n?</a>, J. Number Theory, Vol. 21, No. 1 (1985), pp. 81-100.

%H Joshua Zelinsky, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Zelinsky/zelinsky9.html">Tau Numbers: A Partial Proof of a Conjecture and Other Results </a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.8.

%p with(numtheory):

%p A033950 := proc(n)

%p option remember:

%p local k:

%p if n=1 then

%p return 1:

%p else

%p for k from procname(n-1)+1 do

%p if type(k/tau(k), integer) then

%p return k:

%p end if:

%p end do:

%p end if:

%p end proc:

%p seq(A033950(n), n=1..56); # _Nathaniel Johnston_, May 04 2011

%t Do[If[IntegerQ[n/DivisorSigma[0, n]], Print[n]], {n, 1, 1000}]

%t Select[ Range[559], Mod[ #, DivisorSigma[0, # ]] == 0 &]

%t Select[Range[550], Divisible[ #, DivisorSigma[0, # ]]&] (* _Waldemar Puszkarz_, Jun 10 2016 *)

%o (Magma) [ n: n in [1..540] | n mod #Divisors(n) eq 0 ]; // _Klaus Brockhaus_, Apr 29 2009

%o (PARI) isA033950(n)=n%numdiv(n)==0 \\ _Charles R Greathouse IV_, Jun 10 2011

%o (Haskell)

%o a033950 n = a033950_list !! (n-1)

%o a033950_list = [x | x <- [1..], x `mod` a000005 x == 0]

%o -- _Reinhard Zumkeller_, Dec 28 2011

%o (Python)

%o from sympy import divisor_count

%o print([n for n in range(1, 1001) if not n % divisor_count(n)]) # _Indranil Ghosh_, May 03 2017

%Y Cf. A000005, A000720, A039819, A036762, A051278, A051279, A051280, A036763.

%Y Cf. A235353 (subsequence).

%Y Cf. A054008, A281188.

%K nonn,nice,changed

%O 1,2

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

%E More terms from _Erich Friedman_