login
Numbers whose divisors increase by a factor of at most 2.
54

%I #159 Oct 24 2023 10:10:22

%S 1,2,4,6,8,12,16,18,20,24,28,30,32,36,40,42,48,54,56,60,64,66,72,80,

%T 84,88,90,96,100,104,108,112,120,126,128,132,140,144,150,156,160,162,

%U 168,176,180,192,196,198,200,204,208,210,216,220,224,228,234,240,252,256

%N Numbers whose divisors increase by a factor of at most 2.

%C That is, if the divisors of a number are listed in increasing order, the ratio of adjacent divisors is at most 2. The only odd number in this sequence is 1. Every term appears to be a practical number (A005153). The first practical number not here is 78.

%C Let p1^e1 * p2^e2 * ... * pr^er be the prime factorization of a number, with primes p1 < p2 < ... < pr and ek > 0. Then the number is in this sequence if and only if pk <= 2*Product_{j < k} p_j^e_j. This condition is similar to, but more restrictive than, the condition for practical numbers.

%C The polymath8 project led by Terry Tao refers to these numbers as "2-densely divisible". In general they say that n is y-densely divisible if its divisors increase by a factor of y or less, or equivalently, if for every R with 1 <= R <= n, there is a divisor in the interval [R/y,R]. They use this as a weakening of the condition that n be y-smooth. - _David S. Metzler_, Jul 02 2013

%C Is this the same as numbers k with the property that the symmetric representation of sigma(k) has only one part? If not, where is the first place these sequences differ? (cf. A237593). - _Omar E. Pol_, Mar 06 2014

%C Yes, the sequence so defined is the same as this sequence; see proof in the links. - _Hartmut F. W. Hoft_, Nov 26 2014

%C Saias (1997) called these terms "2-dense numbers" and proved that if N(x) is the number of terms not exceeding x, then there are two positive constants c_1 and c_2 such that c_1 * x/log_2(x) <= N(x) <= c_2 * x/log_2(x) for all x >= 2. - _Amiram Eldar_, Jul 23 2020

%C Weingartner (2015, 2019) showed that N(x) = c*x/log(x) + O(x/(log(x))^2), where c = 1.224830... As a result, a(n) = C*n*log(n*log(n)) + O(n), where C = 1/c = 0.816439... - _Andreas Weingartner_, Jun 22 2021

%H Alois P. Heinz, <a href="/A174973/b174973.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)

%H José Manuel Rodríguez Caballero, <a href="http://math.colgate.edu/~integers/u2/u2.Abstract.html">Jordan's Expansion of the Reciprocal of Theta Functions and 2-densely Divisible Numbers</a>, Integers, Vol. 20 (2020), Article A2.

%H Hartmut F. W. Hoft, <a href="/A174973/a174973.pdf">Proof of a conjecture</a>.

%H Hartmut F. W. Hoft, <a href="/A174973/a174973_1.pdf">Proof of a second conjecture</a>.

%H Eric Saias, <a href="https://doi.org/10.1006/jnth.1997.2057">Entiers à diviseurs denses 1</a>, Journal of Number Theory, Vol. 62, No. 1 (1997), pp. 163-191.

%H Terence Tao, <a href="http://terrytao.wordpress.com/2013/06/18/a-truncated-elementary-selberg-sieve-of-pintz/">A Truncated Elementary Selberg Sieve of Pintz</a>. (blog entry defining y-densely divisible)

%H Terence Tao et al., <a href="http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes">Polymath8 home page</a>.

%H Andreas Weingartner, <a href="https://doi.org/10.1093/qmath/hav006">Practical numbers and the distribution of divisors</a>, The Quarterly Journal of Mathematics, Vol. 66, No. 2 (2015), pp. 743-758; <a href="https://arxiv.org/abs/1405.2585">arXiv preprint</a>, arXiv:1405.2585 [math.NT], 2014-2015.

%H Andreas Weingartner, <a href="https://doi.org/10.1090/mcom/3402">On the constant factor in several related asymptotic estimates</a>, Math. Comp., Vol. 88, No. 318 (2019), pp. 1883-1902; <a href="https://arxiv.org/abs/1705.06349">arXiv preprint</a>, arXiv:1705.06349 [math.NT], 2017-2018.

%H Andreas Weingartner, <a href="https://arxiv.org/abs/2101.11585">The number of prime factors of integers with dense divisors</a>, arXiv:2101.11585 [math.NT], 2021.

%H Andreas Weingartner, <a href="https://arxiv.org/abs/2303.16819">Uniform distribution of alpha*n modulo one for a family of integer sequences</a>, arXiv:2303.16819 [math.NT], 2023.

%F a(n) = A047836(n) / 2. - _Reinhard Zumkeller_, Sep 28 2011

%F a(n) = C*n*log(n*log(n)) + O(n), where C = 0.816439... (see comments). - _Andreas Weingartner_, Jun 23 2021

%e The divisors of 12 are 1, 2, 3, 4, 6, 12. The ratios of adjacent divisors is 2, 3/2, 4/3, 3/2, and 2, which are all <= 2. Hence 12 is in this sequence.

%e Example from _Omar E. Pol_, Mar 06 2014: (Start)

%e The symmetric representation of sigma(6) = 12 in the first quadrant looks like this:

%e y

%e .

%e ._ _ _ _

%e |_ _ _ |_

%e . | |_

%e . |_ _ |

%e . | |

%e . | |

%e . . . . . |_| . . x

%e .

%e 6 is in the sequence because the symmetric representation of sigma(6) = 12 has only one part. The 6th row of A237593 is [4, 1, 1, 1, 1, 4] and the 5th row of A237593 is [3, 2, 2, 3] therefore between both symmetric Dyck paths there is only one region (or part) of size 12.

%e 70 is not in the sequence because the symmetric representation of sigma(70) = 144 has three parts. The 70th row of A237593 is [36, 12, 6, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 6, 12, 36] and the 69th row of A237593 is [35, 12, 7, 4, 2, 3, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 3, 2, 4, 7, 12, 35] therefore between both symmetric Dyck paths there are three regions (or parts) of size [54, 36, 54]. (End)

%p a:= proc() option remember; local k; for k from 1+`if`(n=1, 0,

%p a(n-1)) while (l-> ormap(x-> x, [seq(l[i]>l[i-1]*2, i=2..

%p nops(l))]))(sort([(numtheory[divisors](k))[]])) do od; k

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jul 27 2018

%t OK[n_] := Module[{d=Divisors[n]}, And@@(#<=2& /@ (Rest[d]/Most[d]))]; Select[Range[1000], OK]

%t dif2Q[n_]:=AllTrue[#[[2]]/#[[1]]&/@Partition[Divisors[n],2,1],#<=2&]; Select[Range[300],dif2Q] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, Nov 29 2020 *)

%o (Haskell)

%o a174973 n = a174973_list !! (n-1)

%o a174973_list = filter f [1..] where

%o f n = all (<= 0) $ zipWith (-) (tail divs) (map (* 2) divs)

%o where divs = a027750_row' n

%o -- _Reinhard Zumkeller_, Jun 25 2015, Sep 28 2011

%o (PARI) is(n)=my(d=divisors(n));for(i=2,#d,if(d[i]>2*d[i-1],return(0)));1 \\ _Charles R Greathouse IV_, Jul 06 2013

%o (Magma) [k:k in [1..260]|forall{i:i in [1..#Divisors(k)-1]|d[i+1]/d[i] le 2 where d is Divisors(k)}]; // _Marius A. Burtea_, Jan 09 2020

%o (Python)

%o from sympy import divisors

%o def ok(n):

%o d = divisors(n)

%o return all(d[i]/d[i-1] <= 2 for i in range(1, len(d)))

%o print(list(filter(ok, range(1, 257)))) # _Michael S. Branicky_, Jun 22 2021

%Y Subsequence of A196149 and of A071562. A000396 and A000079 are subsequences.

%Y Cf. A027750, A047836, A237593, A365429 (characteristic function).

%Y Column 1 of A240062.

%Y First differs from A103288 and A125225 at a(23). First differs from A005153 at a(24).

%K nonn

%O 1,2

%A _T. D. Noe_, Apr 02 2010

%E Edited by _N. J. A. Sloane_, Sep 09 2023

%E Edited by _Peter Munn_, Oct 17 2023