cp's OEIS Frontend

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

%I A033950 #161 Apr 09 2025 21:42:08
%S A033950 1,2,8,9,12,18,24,36,40,56,60,72,80,84,88,96,104,108,128,132,136,152,
%T A033950 156,180,184,204,225,228,232,240,248,252,276,288,296,328,344,348,360,
%U A033950 372,376,384,396,424,441,444,448,450,468,472,480,488,492,504,516,536
%N A033950 Refactorable numbers: number of divisors of k divides k. Also known as tau numbers.
%C A033950 Kennedy and Cooper show that this sequence has density zero.
%C A033950 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 A033950 Numbers k such that the equation gcd(k,x) = tau(k) has solutions. - _Benoit Cloitre_, Jun 10 2002
%C A033950 Refactorable numbers are the fixed points of A009230. - _Labos Elemer_, Nov 18 2002
%C A033950 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 A033950 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 A033950 A054008(k) = k mod A000005(k). - _Reinhard Zumkeller_, Sep 17 2014
%C A033950 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 A033950 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 A033950 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
%C A033950 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
%D A033950 Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B12, pp. 102-103.
%D A033950 New Scientist, Sep 05 1998, p. 17, para. 3.
%H A033950 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 A033950 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 A033950 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 A033950 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 A033950 Simon Colton, <a href="http://www.dai.ed.ac.uk/homes/simonco/research/hr/">HR - Automatic Theory Formation in Pure Mathematics</a>.
%H A033950 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 A033950 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 A033950 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 A033950 with(numtheory):
%p A033950 A033950 := proc(n)
%p A033950     option remember:
%p A033950     local k:
%p A033950     if n=1 then
%p A033950         return 1:
%p A033950     else
%p A033950         for k from procname(n-1)+1 do
%p A033950             if type(k/tau(k), integer) then
%p A033950                 return k:
%p A033950             end if:
%p A033950         end do:
%p A033950     end if:
%p A033950 end proc:
%p A033950 seq(A033950(n), n=1..56); # _Nathaniel Johnston_, May 04 2011
%t A033950 Do[If[IntegerQ[n/DivisorSigma[0, n]], Print[n]], {n, 1, 1000}]
%t A033950 Select[ Range[559], Mod[ #, DivisorSigma[0, # ]] == 0 &]
%t A033950 Select[Range[550], Divisible[ #, DivisorSigma[0, # ]]&] (* _Waldemar Puszkarz_, Jun 10 2016 *)
%o A033950 (Magma) [ n: n in [1..540] | n mod #Divisors(n) eq 0 ]; // _Klaus Brockhaus_, Apr 29 2009
%o A033950 (PARI) isA033950(n)=n%numdiv(n)==0 \\ _Charles R Greathouse IV_, Jun 10 2011
%o A033950 (Haskell)
%o A033950 a033950 n = a033950_list !! (n-1)
%o A033950 a033950_list = [x | x <- [1..], x `mod` a000005 x == 0]
%o A033950 -- _Reinhard Zumkeller_, Dec 28 2011
%o A033950 (Python)
%o A033950 from sympy import divisor_count
%o A033950 print([n for n in range(1, 1001) if not n % divisor_count(n)]) # _Indranil Ghosh_, May 03 2017
%Y A033950 Cf. A000005, A000720, A039819, A036762, A051278, A051279, A051280, A036763.
%Y A033950 Cf. A235353 (subsequence).
%Y A033950 Cf. A054008, A281188.
%K A033950 nonn,nice
%O A033950 1,2
%A A033950 Simon Colton (simonco(AT)cs.york.ac.uk)
%E A033950 More terms from _Erich Friedman_