What proportion of positive integers have two factors that differ by 1?
Clash Royale CLAN TAG#URR8PPP
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 = 2cdot 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 dfractextnumber of such integers ge 2 le nxn
=f(x)
$
or find $c$ such that
$lim_n to infty dfractextnumber of such integers ge 2 le nn
=c
$.
My guess is that,
in the latter case,
$c = 0$ or 1,
but I have no idea which is true.
Maybe its
$1-frac1e$.
Note: I have modified this
to not allow 1 as a divisor.
number-theory asymptotics
add a comment |
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 = 2cdot 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 dfractextnumber of such integers ge 2 le nxn
=f(x)
$
or find $c$ such that
$lim_n to infty dfractextnumber of such integers ge 2 le nn
=c
$.
My guess is that,
in the latter case,
$c = 0$ or 1,
but I have no idea which is true.
Maybe its
$1-frac1e$.
Note: I have modified this
to not allow 1 as a divisor.
number-theory asymptotics
26
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
4
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
4
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.
– David Z
Dec 14 at 5:34
4
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
– aschepler
Dec 14 at 12:47
4
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08
add a comment |
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 = 2cdot 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 dfractextnumber of such integers ge 2 le nxn
=f(x)
$
or find $c$ such that
$lim_n to infty dfractextnumber of such integers ge 2 le nn
=c
$.
My guess is that,
in the latter case,
$c = 0$ or 1,
but I have no idea which is true.
Maybe its
$1-frac1e$.
Note: I have modified this
to not allow 1 as a divisor.
number-theory asymptotics
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 = 2cdot 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 dfractextnumber of such integers ge 2 le nxn
=f(x)
$
or find $c$ such that
$lim_n to infty dfractextnumber of such integers ge 2 le nn
=c
$.
My guess is that,
in the latter case,
$c = 0$ or 1,
but I have no idea which is true.
Maybe its
$1-frac1e$.
Note: I have modified this
to not allow 1 as a divisor.
number-theory asymptotics
number-theory asymptotics
edited Dec 14 at 2:55
asked Dec 13 at 23:09
marty cohen
72.3k549127
72.3k549127
26
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
4
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
4
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.
– David Z
Dec 14 at 5:34
4
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
– aschepler
Dec 14 at 12:47
4
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08
add a comment |
26
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
4
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
4
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.
– David Z
Dec 14 at 5:34
4
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
– aschepler
Dec 14 at 12:47
4
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08
26
26
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
4
4
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
4
4
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.
– David Z
Dec 14 at 5:34
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.
– David Z
Dec 14 at 5:34
4
4
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
– aschepler
Dec 14 at 12:47
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
– aschepler
Dec 14 at 12:47
4
4
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08
add a comment |
3 Answers
3
active
oldest
votes
Every even number has consecutive factors: $1$ and $2$.
No odd number has, because all its factors are odd.
The probability is $1/2$.
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
@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.
– J.G.
Dec 14 at 23:37
|
show 2 more comments
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.
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
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$).
– Veedrac
Dec 14 at 18:00
2
@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.
– Veedrac
Dec 14 at 18:12
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
|
show 6 more comments
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$.
$$beginaligned
d(k,i)&=
sum_j=1^kdelta_(i%(j+1)(j+2))\
c(k,i)&=begincases
0,&d(k,i)>1lor d(k-1,n)=1\
d(k,i),&textelse
endcases
endaligned$$
Where $%$ is the modulo operator and $delta_x$ is the single argument Kronecker delta. The proportion we want is then:
$$p=frac16+lim_ntoinftyfrac1nsum_i=1^nsum_k=2^lfloorsqrtirfloorc(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,frac120-frac160,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^nc$ 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^nc$ match this sequence. So perhaps $sum_i=1^2^nc$ 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 $kequiv0mod3$, i.e. you only need to check every third divisor in Dan's answer.
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3038712%2fwhat-proportion-of-positive-integers-have-two-factors-that-differ-by-1%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Every even number has consecutive factors: $1$ and $2$.
No odd number has, because all its factors are odd.
The probability is $1/2$.
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
@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.
– J.G.
Dec 14 at 23:37
|
show 2 more comments
Every even number has consecutive factors: $1$ and $2$.
No odd number has, because all its factors are odd.
The probability is $1/2$.
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
@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.
– J.G.
Dec 14 at 23:37
|
show 2 more comments
Every even number has consecutive factors: $1$ and $2$.
No odd number has, because all its factors are odd.
The probability is $1/2$.
Every even number has consecutive factors: $1$ and $2$.
No odd number has, because all its factors are odd.
The probability is $1/2$.
answered Dec 13 at 23:38
ajotatxe
53.2k23890
53.2k23890
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
@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.
– J.G.
Dec 14 at 23:37
|
show 2 more comments
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
@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.
– J.G.
Dec 14 at 23:37
22
22
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
Good point. I have become my evil twin by not allowing 1 as a divisor. To make up for this, I have upvoted you.
– marty cohen
Dec 14 at 2:57
30
30
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
This is a much more interesting problem if one specifies '1' may not be a factor.
– user121330
Dec 14 at 14:42
1
1
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
OK, so now how many even numbers have N pairs? (evil grin)
– Carl Witthoft
Dec 14 at 15:22
5
5
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
Units are normally excluded from the definition of factors.
– R..
Dec 14 at 18:31
6
6
@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.
– J.G.
Dec 14 at 23:37
@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.
– J.G.
Dec 14 at 23:37
|
show 2 more comments
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.
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
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$).
– Veedrac
Dec 14 at 18:00
2
@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.
– Veedrac
Dec 14 at 18:12
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
|
show 6 more comments
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.
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
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$).
– Veedrac
Dec 14 at 18:00
2
@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.
– Veedrac
Dec 14 at 18:12
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
|
show 6 more comments
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.
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.
answered Dec 14 at 5:23
Dan
4,49011517
4,49011517
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
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$).
– Veedrac
Dec 14 at 18:00
2
@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.
– Veedrac
Dec 14 at 18:12
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
|
show 6 more comments
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
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$).
– Veedrac
Dec 14 at 18:00
2
@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.
– Veedrac
Dec 14 at 18:12
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
2
2
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
Don't forget that 1/2 gives you the other bound, for the same reason as the original answer
– Eric
Dec 14 at 8:24
6
6
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
True: The product of two consecutive integers is always even, so no odd number can have the property we're looking for.
– Dan
Dec 14 at 13:29
4
4
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$).
– Veedrac
Dec 14 at 18:00
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$).
– Veedrac
Dec 14 at 18:00
2
2
@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.
– Veedrac
Dec 14 at 18:12
@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.
– Veedrac
Dec 14 at 18:12
4
4
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
We can also compute upper bounds using $sum_n=k^infty frac1n(n+1) = frac1k$. 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$.
– Eric M. Schmidt
Dec 15 at 23:08
|
show 6 more comments
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$.
$$beginaligned
d(k,i)&=
sum_j=1^kdelta_(i%(j+1)(j+2))\
c(k,i)&=begincases
0,&d(k,i)>1lor d(k-1,n)=1\
d(k,i),&textelse
endcases
endaligned$$
Where $%$ is the modulo operator and $delta_x$ is the single argument Kronecker delta. The proportion we want is then:
$$p=frac16+lim_ntoinftyfrac1nsum_i=1^nsum_k=2^lfloorsqrtirfloorc(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,frac120-frac160,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^nc$ 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^nc$ match this sequence. So perhaps $sum_i=1^2^nc$ 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 $kequiv0mod3$, i.e. you only need to check every third divisor in Dan's answer.
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
add a comment |
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$.
$$beginaligned
d(k,i)&=
sum_j=1^kdelta_(i%(j+1)(j+2))\
c(k,i)&=begincases
0,&d(k,i)>1lor d(k-1,n)=1\
d(k,i),&textelse
endcases
endaligned$$
Where $%$ is the modulo operator and $delta_x$ is the single argument Kronecker delta. The proportion we want is then:
$$p=frac16+lim_ntoinftyfrac1nsum_i=1^nsum_k=2^lfloorsqrtirfloorc(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,frac120-frac160,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^nc$ 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^nc$ match this sequence. So perhaps $sum_i=1^2^nc$ 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 $kequiv0mod3$, i.e. you only need to check every third divisor in Dan's answer.
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
add a comment |
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$.
$$beginaligned
d(k,i)&=
sum_j=1^kdelta_(i%(j+1)(j+2))\
c(k,i)&=begincases
0,&d(k,i)>1lor d(k-1,n)=1\
d(k,i),&textelse
endcases
endaligned$$
Where $%$ is the modulo operator and $delta_x$ is the single argument Kronecker delta. The proportion we want is then:
$$p=frac16+lim_ntoinftyfrac1nsum_i=1^nsum_k=2^lfloorsqrtirfloorc(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,frac120-frac160,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^nc$ 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^nc$ match this sequence. So perhaps $sum_i=1^2^nc$ 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 $kequiv0mod3$, i.e. you only need to check every third divisor in Dan's answer.
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$.
$$beginaligned
d(k,i)&=
sum_j=1^kdelta_(i%(j+1)(j+2))\
c(k,i)&=begincases
0,&d(k,i)>1lor d(k-1,n)=1\
d(k,i),&textelse
endcases
endaligned$$
Where $%$ is the modulo operator and $delta_x$ is the single argument Kronecker delta. The proportion we want is then:
$$p=frac16+lim_ntoinftyfrac1nsum_i=1^nsum_k=2^lfloorsqrtirfloorc(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,frac120-frac160,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^nc$ 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^nc$ match this sequence. So perhaps $sum_i=1^2^nc$ 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 $kequiv0mod3$, i.e. you only need to check every third divisor in Dan's answer.
edited Dec 19 at 14:37
answered Dec 17 at 18:20
Jam
4,93711431
4,93711431
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
add a comment |
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
Please try to avoid making very many edits.
– quid♦
Dec 19 at 14:48
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3038712%2fwhat-proportion-of-positive-integers-have-two-factors-that-differ-by-1%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
26
There are $365.2425$ days per year on average when taking leap year into account.
– JMoravitz
Dec 13 at 23:23
4
A list of such numbers can be found at oeis.org/A088723
– Dan
Dec 14 at 5:04
4
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.
– David Z
Dec 14 at 5:34
4
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
– aschepler
Dec 14 at 12:47
4
Slightly better approximation: 0.22194814. I approximately measured the density in the range $[k, k+10^10)$ where $k=345678912345678$.
– Veedrac
Dec 14 at 16:08