57
$\begingroup$

What proportion of positive integers have two factors that differ by 1?

This question occurred to me while trying to figure out why there are 7 days in a week.

I looked at 364, the number of days closest to a year (there are about 364.2422 days in a year, iirc). Since $364 = 2\cdot 2 \cdot 7 \cdot 13$, the number of possible number that evenly divide a year are 2, 4, 7, 13, 14, 26, 28, and larger.

Given this, 7 looks reasonable - 2 and 4 are too short and 13 is too long.

Anyway, I noticed that 13 and 14 are there, and wondered how often this happens.

I wasn't able to figure out a nice way to specify the probability (as in a Hardy-Littlewood product), and wasn't able to do it from the inverse direction (i.e., sort of a sieve with n(n+1) going into the array of integers).

Ideally, I would like an asymptotic function f(x) such that $\lim_{n \to \infty} \dfrac{\text{number of such integers } \ge 2 \le nx}{n} =f(x) $ or find $c$ such that $\lim_{n \to \infty} \dfrac{\text{number of such integers } \ge 2 \le n}{n} =c $.

My guess is that, in the latter case, $c = 0$ or 1, but I have no idea which is true. Maybe its $1-\frac1{e}$.

Note: I have modified this to not allow 1 as a divisor.

$\endgroup$
  • 26
    $\begingroup$ There are $365.2425$ days per year on average when taking leap year into account. $\endgroup$ – JMoravitz Dec 13 '18 at 23:23
  • 4
    $\begingroup$ A list of such numbers can be found at oeis.org/A088723 $\endgroup$ – Dan Dec 14 '18 at 5:04
  • 4
    $\begingroup$ I presume this doesn't constitute an answer for what you wanted, but I wrote a program to do a brute-force count and going up to $10^6$ I find 221944 numbers with this property; or up to $10^7$ I find 2219451. Perhaps that number will give someone an idea. $\endgroup$ – David Z Dec 14 '18 at 5:34
  • 4
    $\begingroup$ History of the seven-day week (probably because it's close to 1/4 a lunar month, rather than 1/52 an astronomical year): en.wikipedia.org/wiki/Week#History $\endgroup$ – aschepler Dec 14 '18 at 12:47
  • 4
    $\begingroup$ Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^{10})$ where $k=345678912345678$. $\endgroup$ – Veedrac Dec 14 '18 at 16:08
86
$\begingroup$

Every even number has consecutive factors: $1$ and $2$.

No odd number has, because all its factors are odd.

The probability is $1/2$.

$\endgroup$
  • 22
    $\begingroup$ Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you. $\endgroup$ – marty cohen Dec 14 '18 at 2:57
  • 30
    $\begingroup$ This is a much more interesting problem if one specifies '1' may not be a factor. $\endgroup$ – user121330 Dec 14 '18 at 14:42
  • 1
    $\begingroup$ OK, so now how many even numbers have N pairs? (evil grin) $\endgroup$ – Carl Witthoft Dec 14 '18 at 15:22
  • 5
    $\begingroup$ Units are normally excluded from the definition of factors. $\endgroup$ – R.. Dec 14 '18 at 18:31
  • 6
    $\begingroup$ @R. Not in my experience of number theory (though in more general contexts it would be reasonable). The number whose factors you're seeking, on the other hand, is excluded from "proper" factors. $\endgroup$ – J.G. Dec 14 '18 at 23:37
33
$\begingroup$

What kind of numbers have this property?

  • All multiples of 6 (because 6 = 2 × 3). So that's 1/6 of the integers.
  • All multiples of 12 (12 = 3 × 4), but these have already been counted as multiples of 6.
  • All multiples of 20 (20 = 4 × 5), so add 1/20 of the integers. But we've double-counted multiples of 60 (LCD of 6 and 20), so subtract 1/60. This gives us 1/6 + 1/20 - 1/60 = 1/5.
  • All multiples of 30 (5 × 6) or 42 (6 × 7), but again, these have already been counted as multiples of 6.
  • All multiples of 56 (7 × 8), but don't double-count the ones that are also multiples of 6 or 20. If I did the arithmetic correctly, this brings us up to 22/105.
  • All multiples of 72 (8 × 9) or 90 (9 × 10), but these are already multiples of 6.
  • All multiples of 110 (10 × 11), being careful not to double-count multiples of 6, 20, or 56. We're now at 491/2310.

Continue the pattern to get a lower bound on the probability. I bet it converges to something, but I haven't bothered to compute what.

$\endgroup$
  • 2
    $\begingroup$ Don't forget that 1/2 gives you the other bound, for the same reason as the original answer $\endgroup$ – Eric Dec 14 '18 at 8:24
  • 6
    $\begingroup$ True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for. $\endgroup$ – Dan Dec 14 '18 at 13:29
  • 4
    $\begingroup$ Continuing until 190×191, you get a density of approximately 0.2215. It gets exponentially harder to calculate as you go along, and doesn't converge amazingly fast. (Exact fraction $30692078612850182537626772507400566302461540183482511947993/138565669082349191587117161961128738469412352721071780196786$). $\endgroup$ – Veedrac Dec 14 '18 at 18:00
  • 2
    $\begingroup$ @Dan I doubt it. The 0.22194814 I measured manually has fairly low error (I'd guess 4-5 s.f.). Using an approximate version of this post (ignoring terms $<10^{-11}$) I also get 0.221941 at 10882×10883, which is definitely imprecise but lends credence to that ballpark. $\endgroup$ – Veedrac Dec 14 '18 at 18:12
  • 4
    $\begingroup$ We can also compute upper bounds using $\sum_{n=k}^\infty \frac{1}{n(n+1)} = \frac{1}{k}$. Let $s_k$ be the lower bound computed using the terms up to $k \times (k+1)$. Then, an upper bound is $s_k + 1/(k+1)$. For instance, if we apply this to Veedrac's estimate for $10882 \times 10883$, we get an approximate upper bound of $0.221941 + 1/10883$, which is about $0.222033$. $\endgroup$ – Eric M. Schmidt Dec 15 '18 at 23:08
7
$\begingroup$

I've used Dan's idea to attempt to formalise the problem some more. Define $d(k,i)$ as the number of pairs of consecutive divisors of $i$ up to $(k+2)$. Then $c(k,i)$ stops $d$ from over-counting and is the indicator function for whether $(k+1)$, $(k+2)$ are the first pair of consecutive divisors of $i$.

$$\begin{aligned} d(k,i)&= \sum_{j=1}^{k}\delta_{(i\%(j+1)(j+2))}\\ c(k,i)&=\begin{cases} 0,&d(k,i)>1\lor d(k-1,n)=1\\ d(k,i),&\text{else} \end{cases} \end{aligned}$$

Where $\%$ is the modulo operator and $\delta_x$ is the single argument Kronecker delta. The proportion we want is then:

$$p=\frac16+\lim_{n\to\infty}\frac1{n}\sum_{i=1}^n\sum_{k=2}^{\lfloor\sqrt{i}\rfloor}c(k,i)\\$$

The sum over $k$ represents different divisors, while the sum over $i$ represents different dividends. Here is a python script for a former rearrangement of the equations. They agree with the $0.2219$ estimates others have provided. Bear in mind they're slow but can potentially be manipulated.

To proceed further, we could try simplifying $c(k,i)$ or sieve techniques. Swapping round the sums is equivalent to how Dan has found the values $\frac16,0,\frac1{20}-\frac1{60},\ldots$ for $k=1,2,3,\ldots$. Similarly, we can swap round the sum operators, then fix $k$ and look at the sequence of partial sums of $\sum_{i=1}^nc$.

I used $n$ in powers of $2$, to make the sequence manageable. By comparing the partial sums of $\sum_{i=1}^{2^n}c$ with sequences on OEIS, I found that when $k=1$, the nonzero partial sums of the sequence match this sequence. But when $k=3$, the nonzero partial sums of $\sum_{i=1}^{2^n}c$ match this sequence. So perhaps $\sum_{i=1}^{2^n}c$ can be expressed as the expansions of rational functions.

From playing with the output of the code, it seems as though $\sum_{i=1}^nc$ is nonzero iff $k\equiv0\mod3$, i.e. you only need to check every third divisor in Dan's answer.

$\endgroup$
  • $\begingroup$ Please try to avoid making very many edits. $\endgroup$ – quid Dec 19 '18 at 14:48

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.