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