A sequence that avoids both arithmetic and geometric progressions
$begingroup$
Sequences that avoid arithmetic progressions have been studied, e.g., "Sequences Containing No 3-Term Arithmetic Progressions," Janusz Dybizbański, 2012, journal link.
I started to explore sequences that avoid both arithmetic and geometric progressions,
i.e., avoid $x, x+c, x+2c$ and avoid $y, c y, c^2 y$ anywhere in the sequence
(not necessarily consecutively).
Starting with $(1,2)$, one cannot extend with $3$ because $(1,2,3)$ forms an
arithemtical progression, and one cannot extend with $4$ because $(1,2,4)$ is a geometric
progression. But $(1,2,5)$ is fine.
Continuing in the same manner leads to the following "greedy" sequence:
$$1, 2, 5, 6, 12, 13, 15, 16, 32, 33, 35, 39, 40, 42, 56, 81, 84, 85, 88,$$
$$90, 93, 94, 108, 109, 113, 115, 116, 159, 189, 207, 208, 222, ldots$$
This sequence is not in the OEIS.
Here are a few questions:
Q1. What is its growth rate?
Q2. Does $sum_{i=1}^infty 1/s_i$ converge? (Where $s_i$ is the $i$-th term of the above
sequence.)
Q3. If it does, does it converge to e?
Update: No. The sum appears to be approximately $2.73 > e$, as per
@MichaelStocker and @Turambar.
That is wild numerical speculation. The first 457 terms (the extent
of the graph above) sum to 2.70261.
Addendum. 11Jul2014. Starting with $(0,1)$ rather than $(1,2)$ renders
a direct hit on OEIS A225571.
sequences-and-series number-theory
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
$endgroup$
|
show 7 more comments
$begingroup$
Sequences that avoid arithmetic progressions have been studied, e.g., "Sequences Containing No 3-Term Arithmetic Progressions," Janusz Dybizbański, 2012, journal link.
I started to explore sequences that avoid both arithmetic and geometric progressions,
i.e., avoid $x, x+c, x+2c$ and avoid $y, c y, c^2 y$ anywhere in the sequence
(not necessarily consecutively).
Starting with $(1,2)$, one cannot extend with $3$ because $(1,2,3)$ forms an
arithemtical progression, and one cannot extend with $4$ because $(1,2,4)$ is a geometric
progression. But $(1,2,5)$ is fine.
Continuing in the same manner leads to the following "greedy" sequence:
$$1, 2, 5, 6, 12, 13, 15, 16, 32, 33, 35, 39, 40, 42, 56, 81, 84, 85, 88,$$
$$90, 93, 94, 108, 109, 113, 115, 116, 159, 189, 207, 208, 222, ldots$$
This sequence is not in the OEIS.
Here are a few questions:
Q1. What is its growth rate?
Q2. Does $sum_{i=1}^infty 1/s_i$ converge? (Where $s_i$ is the $i$-th term of the above
sequence.)
Q3. If it does, does it converge to e?
Update: No. The sum appears to be approximately $2.73 > e$, as per
@MichaelStocker and @Turambar.
That is wild numerical speculation. The first 457 terms (the extent
of the graph above) sum to 2.70261.
Addendum. 11Jul2014. Starting with $(0,1)$ rather than $(1,2)$ renders
a direct hit on OEIS A225571.
sequences-and-series number-theory
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
$endgroup$
6
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
3
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
2
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
1
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
1
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14
|
show 7 more comments
$begingroup$
Sequences that avoid arithmetic progressions have been studied, e.g., "Sequences Containing No 3-Term Arithmetic Progressions," Janusz Dybizbański, 2012, journal link.
I started to explore sequences that avoid both arithmetic and geometric progressions,
i.e., avoid $x, x+c, x+2c$ and avoid $y, c y, c^2 y$ anywhere in the sequence
(not necessarily consecutively).
Starting with $(1,2)$, one cannot extend with $3$ because $(1,2,3)$ forms an
arithemtical progression, and one cannot extend with $4$ because $(1,2,4)$ is a geometric
progression. But $(1,2,5)$ is fine.
Continuing in the same manner leads to the following "greedy" sequence:
$$1, 2, 5, 6, 12, 13, 15, 16, 32, 33, 35, 39, 40, 42, 56, 81, 84, 85, 88,$$
$$90, 93, 94, 108, 109, 113, 115, 116, 159, 189, 207, 208, 222, ldots$$
This sequence is not in the OEIS.
Here are a few questions:
Q1. What is its growth rate?
Q2. Does $sum_{i=1}^infty 1/s_i$ converge? (Where $s_i$ is the $i$-th term of the above
sequence.)
Q3. If it does, does it converge to e?
Update: No. The sum appears to be approximately $2.73 > e$, as per
@MichaelStocker and @Turambar.
That is wild numerical speculation. The first 457 terms (the extent
of the graph above) sum to 2.70261.
Addendum. 11Jul2014. Starting with $(0,1)$ rather than $(1,2)$ renders
a direct hit on OEIS A225571.
sequences-and-series number-theory
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
$endgroup$
Sequences that avoid arithmetic progressions have been studied, e.g., "Sequences Containing No 3-Term Arithmetic Progressions," Janusz Dybizbański, 2012, journal link.
I started to explore sequences that avoid both arithmetic and geometric progressions,
i.e., avoid $x, x+c, x+2c$ and avoid $y, c y, c^2 y$ anywhere in the sequence
(not necessarily consecutively).
Starting with $(1,2)$, one cannot extend with $3$ because $(1,2,3)$ forms an
arithemtical progression, and one cannot extend with $4$ because $(1,2,4)$ is a geometric
progression. But $(1,2,5)$ is fine.
Continuing in the same manner leads to the following "greedy" sequence:
$$1, 2, 5, 6, 12, 13, 15, 16, 32, 33, 35, 39, 40, 42, 56, 81, 84, 85, 88,$$
$$90, 93, 94, 108, 109, 113, 115, 116, 159, 189, 207, 208, 222, ldots$$
This sequence is not in the OEIS.
Here are a few questions:
Q1. What is its growth rate?
Q2. Does $sum_{i=1}^infty 1/s_i$ converge? (Where $s_i$ is the $i$-th term of the above
sequence.)
Q3. If it does, does it converge to e?
Update: No. The sum appears to be approximately $2.73 > e$, as per
@MichaelStocker and @Turambar.
That is wild numerical speculation. The first 457 terms (the extent
of the graph above) sum to 2.70261.
Addendum. 11Jul2014. Starting with $(0,1)$ rather than $(1,2)$ renders
a direct hit on OEIS A225571.
sequences-and-series number-theory
sequences-and-series number-theory
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
edited Jan 6 at 22:49
Joseph O'Rourke
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
asked Jul 7 '14 at 12:02
Joseph O'RourkeJoseph O'Rourke
18.3k351113
18.3k351113
6
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
3
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
2
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
1
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
1
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14
|
show 7 more comments
6
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
3
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
2
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
1
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
1
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14
6
6
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
3
3
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
2
2
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
1
1
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
1
1
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14
|
show 7 more comments
2 Answers
2
active
oldest
votes
$begingroup$
$color{brown}{textbf{HINT}}$
Denote the target sequence ${F_3(n)}$ and let us try to estimate the probability $P(N)}$ that natural number belongs to ${F_3}.$
Suppose
$$F_3(1)=1,quad F_3(2)=2,quad P(1)=P(2)=P(5) = P(6) = 1,\ P(3)=P(4)=P(7)=P(8)=0,tag1$$
$$V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(N) = left[V^{-1}(N)right].tag2$$
Let $P_a(N)$ is the probability that N does not belong to arithmetic progression and $P_g(N)$ is the similar probability for geometric progressions.
Suppose
$$P(N) = P_a(N)P_g(N)).tag3$$
$color{brown}{textbf{Arithmetic Probability estimation.}}$
Suppose
$$P_a(N)=prodlimits_{k=1}^{[N/2]}P_a(N,k),tag4$$
where $P_a(N,k)$ is the probability that arithmetic progression ${N-2k,N-k, N}$ does not exist for any $j.$
Suppose
$$P_a(N,k) = big(1-P(N-2k)big)big((1-P(N-k)big).tag5$$
$color{brown}{textbf{Geometric Probability estimation.}}$
Suppose
$$P_g(N)=prodlimits_{k=1}^{left[,sqrt Nn,right]}P_g(N,k),tag6$$
where $P_g(N,k)$ is the probability that geometric progression $left(dfrac{N}{k^2}, dfrac Nk, Nright}$ with the denominator $k$ does not exist for all $i,j.$
Taking in account that the geometric progression can exist only if $k^2,| N,$ suppose
$$P_g(N,k) = left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right).tag7$$
$color{brown}{textbf{Common model.}}$
Common model can be simplified to next one,
begin{cases}
P(N) = 1-prodlimits_{k=1}^{[N/2-1]}Big(1-big(1-P(N-2k)big)big(1-P(N-k)big)Big)\
timesprodlimits_{k=1}^{left[sqrt Nright]}left(1-left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right)right)\[4pt]
P(1)=P(2)=P(5) = P(6) = 1,quad P(3)=P(4)=P(7)=P(8)=0\
V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(n) = left[V^{-1}(n)right].tag8
end{cases}
Looking the solution in the form of
$$left{begin{align}
&P(N)=P_v(N),quadtext{where}quad v=left[dfrac{N-1 mod 4}2right],\[4pt]
&P_0(N)=
begin{cases}
1,quadtext{if}quad N<9\
cN^{-s},quadtext{otherwise}
end{cases}\[4pt]
&P_1(N)=
begin{cases}
0,quadtext{if}quad N<9\
dN^{-t},quadtext{otherwise}
end{cases}
end{align}right.tag9$$
then
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_0(N-4k)big)big(1-P_1(N-2k)big)Big)\
&×Big(1-big(1-P_1(N-4k-2)big)big(1-P_0(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_0left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_1left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_1left(dfrac{N}{4k^2}right)right)
left(1-P_0left(dfrac{N}{2k}right)right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_1(N-4k)big)big(1-P_0(N-2k)big)Big)\
&&Big(1-big(1-P_0(N-4k-2)big)big(1-P_1(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_1left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_0left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_0left(dfrac{N}{4k^2}right)right)
left(1-P_1left(dfrac{N}{2k}right)right)right).
end{cases}tag{10}$$
Taking in account $(9),$ can be written
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k-1)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-c(N-4k)^{-s}big)big(1-d(N-2k)^{-t}big)Big)\
&×Big(1-big(1-d(N-4k-2)^{-t}big)big(1-c(N-2k-1)^{-s}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}cleft(dfrac{N}{(2k-1)^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k-1}right)^{-t}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}dleft(dfrac{N}{4k^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k}right)^{-s}right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-d(N-4k)^{-t}big)big(1-(N-2k)^{-s}big)Big)\
&&Big(1-big(1-(N-4k-2)^{-s}big)big(1-d(N-2k-1)^{-t}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}dleft(dfrac{N}{(2k-1)^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k-1}right)^{-s}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}cleft(dfrac{N}{4k^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k}right)^{-t}right)right).
end{cases}tag{11}$$
Model $(11)$ should be checked theoretically and practically, but it gives the approach to the required estimations.
The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
$endgroup$
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
add a comment |
$begingroup$
Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because
a paper discussing this conjecture was just published, I thought I would mention it:
Erdős Conjecture (1940s or 1950s). If $A subset mathbb{N}$
satisfies $sum_{n in A} frac{1}{n}= infty$, then
$A$ contains arbitrarily long arithmetic progressions.
In
- Grochow, Joshua. "New applications of the polynomial method: The cap
set conjecture and beyond." Bulletin of the American Mathematical
Society, Vol.56, No.1, Jan. 2019,
he says:
"It remains open even to prove that a set $A$ satisfying the hypothesis contains $3$-term arithmetic progressions."
$endgroup$
add a comment |
Your Answer
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%2f858918%2fa-sequence-that-avoids-both-arithmetic-and-geometric-progressions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$color{brown}{textbf{HINT}}$
Denote the target sequence ${F_3(n)}$ and let us try to estimate the probability $P(N)}$ that natural number belongs to ${F_3}.$
Suppose
$$F_3(1)=1,quad F_3(2)=2,quad P(1)=P(2)=P(5) = P(6) = 1,\ P(3)=P(4)=P(7)=P(8)=0,tag1$$
$$V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(N) = left[V^{-1}(N)right].tag2$$
Let $P_a(N)$ is the probability that N does not belong to arithmetic progression and $P_g(N)$ is the similar probability for geometric progressions.
Suppose
$$P(N) = P_a(N)P_g(N)).tag3$$
$color{brown}{textbf{Arithmetic Probability estimation.}}$
Suppose
$$P_a(N)=prodlimits_{k=1}^{[N/2]}P_a(N,k),tag4$$
where $P_a(N,k)$ is the probability that arithmetic progression ${N-2k,N-k, N}$ does not exist for any $j.$
Suppose
$$P_a(N,k) = big(1-P(N-2k)big)big((1-P(N-k)big).tag5$$
$color{brown}{textbf{Geometric Probability estimation.}}$
Suppose
$$P_g(N)=prodlimits_{k=1}^{left[,sqrt Nn,right]}P_g(N,k),tag6$$
where $P_g(N,k)$ is the probability that geometric progression $left(dfrac{N}{k^2}, dfrac Nk, Nright}$ with the denominator $k$ does not exist for all $i,j.$
Taking in account that the geometric progression can exist only if $k^2,| N,$ suppose
$$P_g(N,k) = left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right).tag7$$
$color{brown}{textbf{Common model.}}$
Common model can be simplified to next one,
begin{cases}
P(N) = 1-prodlimits_{k=1}^{[N/2-1]}Big(1-big(1-P(N-2k)big)big(1-P(N-k)big)Big)\
timesprodlimits_{k=1}^{left[sqrt Nright]}left(1-left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right)right)\[4pt]
P(1)=P(2)=P(5) = P(6) = 1,quad P(3)=P(4)=P(7)=P(8)=0\
V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(n) = left[V^{-1}(n)right].tag8
end{cases}
Looking the solution in the form of
$$left{begin{align}
&P(N)=P_v(N),quadtext{where}quad v=left[dfrac{N-1 mod 4}2right],\[4pt]
&P_0(N)=
begin{cases}
1,quadtext{if}quad N<9\
cN^{-s},quadtext{otherwise}
end{cases}\[4pt]
&P_1(N)=
begin{cases}
0,quadtext{if}quad N<9\
dN^{-t},quadtext{otherwise}
end{cases}
end{align}right.tag9$$
then
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_0(N-4k)big)big(1-P_1(N-2k)big)Big)\
&×Big(1-big(1-P_1(N-4k-2)big)big(1-P_0(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_0left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_1left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_1left(dfrac{N}{4k^2}right)right)
left(1-P_0left(dfrac{N}{2k}right)right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_1(N-4k)big)big(1-P_0(N-2k)big)Big)\
&&Big(1-big(1-P_0(N-4k-2)big)big(1-P_1(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_1left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_0left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_0left(dfrac{N}{4k^2}right)right)
left(1-P_1left(dfrac{N}{2k}right)right)right).
end{cases}tag{10}$$
Taking in account $(9),$ can be written
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k-1)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-c(N-4k)^{-s}big)big(1-d(N-2k)^{-t}big)Big)\
&×Big(1-big(1-d(N-4k-2)^{-t}big)big(1-c(N-2k-1)^{-s}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}cleft(dfrac{N}{(2k-1)^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k-1}right)^{-t}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}dleft(dfrac{N}{4k^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k}right)^{-s}right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-d(N-4k)^{-t}big)big(1-(N-2k)^{-s}big)Big)\
&&Big(1-big(1-(N-4k-2)^{-s}big)big(1-d(N-2k-1)^{-t}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}dleft(dfrac{N}{(2k-1)^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k-1}right)^{-s}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}cleft(dfrac{N}{4k^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k}right)^{-t}right)right).
end{cases}tag{11}$$
Model $(11)$ should be checked theoretically and practically, but it gives the approach to the required estimations.
The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
$endgroup$
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
add a comment |
$begingroup$
$color{brown}{textbf{HINT}}$
Denote the target sequence ${F_3(n)}$ and let us try to estimate the probability $P(N)}$ that natural number belongs to ${F_3}.$
Suppose
$$F_3(1)=1,quad F_3(2)=2,quad P(1)=P(2)=P(5) = P(6) = 1,\ P(3)=P(4)=P(7)=P(8)=0,tag1$$
$$V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(N) = left[V^{-1}(N)right].tag2$$
Let $P_a(N)$ is the probability that N does not belong to arithmetic progression and $P_g(N)$ is the similar probability for geometric progressions.
Suppose
$$P(N) = P_a(N)P_g(N)).tag3$$
$color{brown}{textbf{Arithmetic Probability estimation.}}$
Suppose
$$P_a(N)=prodlimits_{k=1}^{[N/2]}P_a(N,k),tag4$$
where $P_a(N,k)$ is the probability that arithmetic progression ${N-2k,N-k, N}$ does not exist for any $j.$
Suppose
$$P_a(N,k) = big(1-P(N-2k)big)big((1-P(N-k)big).tag5$$
$color{brown}{textbf{Geometric Probability estimation.}}$
Suppose
$$P_g(N)=prodlimits_{k=1}^{left[,sqrt Nn,right]}P_g(N,k),tag6$$
where $P_g(N,k)$ is the probability that geometric progression $left(dfrac{N}{k^2}, dfrac Nk, Nright}$ with the denominator $k$ does not exist for all $i,j.$
Taking in account that the geometric progression can exist only if $k^2,| N,$ suppose
$$P_g(N,k) = left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right).tag7$$
$color{brown}{textbf{Common model.}}$
Common model can be simplified to next one,
begin{cases}
P(N) = 1-prodlimits_{k=1}^{[N/2-1]}Big(1-big(1-P(N-2k)big)big(1-P(N-k)big)Big)\
timesprodlimits_{k=1}^{left[sqrt Nright]}left(1-left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right)right)\[4pt]
P(1)=P(2)=P(5) = P(6) = 1,quad P(3)=P(4)=P(7)=P(8)=0\
V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(n) = left[V^{-1}(n)right].tag8
end{cases}
Looking the solution in the form of
$$left{begin{align}
&P(N)=P_v(N),quadtext{where}quad v=left[dfrac{N-1 mod 4}2right],\[4pt]
&P_0(N)=
begin{cases}
1,quadtext{if}quad N<9\
cN^{-s},quadtext{otherwise}
end{cases}\[4pt]
&P_1(N)=
begin{cases}
0,quadtext{if}quad N<9\
dN^{-t},quadtext{otherwise}
end{cases}
end{align}right.tag9$$
then
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_0(N-4k)big)big(1-P_1(N-2k)big)Big)\
&×Big(1-big(1-P_1(N-4k-2)big)big(1-P_0(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_0left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_1left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_1left(dfrac{N}{4k^2}right)right)
left(1-P_0left(dfrac{N}{2k}right)right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_1(N-4k)big)big(1-P_0(N-2k)big)Big)\
&&Big(1-big(1-P_0(N-4k-2)big)big(1-P_1(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_1left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_0left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_0left(dfrac{N}{4k^2}right)right)
left(1-P_1left(dfrac{N}{2k}right)right)right).
end{cases}tag{10}$$
Taking in account $(9),$ can be written
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k-1)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-c(N-4k)^{-s}big)big(1-d(N-2k)^{-t}big)Big)\
&×Big(1-big(1-d(N-4k-2)^{-t}big)big(1-c(N-2k-1)^{-s}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}cleft(dfrac{N}{(2k-1)^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k-1}right)^{-t}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}dleft(dfrac{N}{4k^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k}right)^{-s}right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-d(N-4k)^{-t}big)big(1-(N-2k)^{-s}big)Big)\
&&Big(1-big(1-(N-4k-2)^{-s}big)big(1-d(N-2k-1)^{-t}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}dleft(dfrac{N}{(2k-1)^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k-1}right)^{-s}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}cleft(dfrac{N}{4k^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k}right)^{-t}right)right).
end{cases}tag{11}$$
Model $(11)$ should be checked theoretically and practically, but it gives the approach to the required estimations.
The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
$endgroup$
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
add a comment |
$begingroup$
$color{brown}{textbf{HINT}}$
Denote the target sequence ${F_3(n)}$ and let us try to estimate the probability $P(N)}$ that natural number belongs to ${F_3}.$
Suppose
$$F_3(1)=1,quad F_3(2)=2,quad P(1)=P(2)=P(5) = P(6) = 1,\ P(3)=P(4)=P(7)=P(8)=0,tag1$$
$$V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(N) = left[V^{-1}(N)right].tag2$$
Let $P_a(N)$ is the probability that N does not belong to arithmetic progression and $P_g(N)$ is the similar probability for geometric progressions.
Suppose
$$P(N) = P_a(N)P_g(N)).tag3$$
$color{brown}{textbf{Arithmetic Probability estimation.}}$
Suppose
$$P_a(N)=prodlimits_{k=1}^{[N/2]}P_a(N,k),tag4$$
where $P_a(N,k)$ is the probability that arithmetic progression ${N-2k,N-k, N}$ does not exist for any $j.$
Suppose
$$P_a(N,k) = big(1-P(N-2k)big)big((1-P(N-k)big).tag5$$
$color{brown}{textbf{Geometric Probability estimation.}}$
Suppose
$$P_g(N)=prodlimits_{k=1}^{left[,sqrt Nn,right]}P_g(N,k),tag6$$
where $P_g(N,k)$ is the probability that geometric progression $left(dfrac{N}{k^2}, dfrac Nk, Nright}$ with the denominator $k$ does not exist for all $i,j.$
Taking in account that the geometric progression can exist only if $k^2,| N,$ suppose
$$P_g(N,k) = left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right).tag7$$
$color{brown}{textbf{Common model.}}$
Common model can be simplified to next one,
begin{cases}
P(N) = 1-prodlimits_{k=1}^{[N/2-1]}Big(1-big(1-P(N-2k)big)big(1-P(N-k)big)Big)\
timesprodlimits_{k=1}^{left[sqrt Nright]}left(1-left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right)right)\[4pt]
P(1)=P(2)=P(5) = P(6) = 1,quad P(3)=P(4)=P(7)=P(8)=0\
V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(n) = left[V^{-1}(n)right].tag8
end{cases}
Looking the solution in the form of
$$left{begin{align}
&P(N)=P_v(N),quadtext{where}quad v=left[dfrac{N-1 mod 4}2right],\[4pt]
&P_0(N)=
begin{cases}
1,quadtext{if}quad N<9\
cN^{-s},quadtext{otherwise}
end{cases}\[4pt]
&P_1(N)=
begin{cases}
0,quadtext{if}quad N<9\
dN^{-t},quadtext{otherwise}
end{cases}
end{align}right.tag9$$
then
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_0(N-4k)big)big(1-P_1(N-2k)big)Big)\
&×Big(1-big(1-P_1(N-4k-2)big)big(1-P_0(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_0left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_1left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_1left(dfrac{N}{4k^2}right)right)
left(1-P_0left(dfrac{N}{2k}right)right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_1(N-4k)big)big(1-P_0(N-2k)big)Big)\
&&Big(1-big(1-P_0(N-4k-2)big)big(1-P_1(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_1left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_0left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_0left(dfrac{N}{4k^2}right)right)
left(1-P_1left(dfrac{N}{2k}right)right)right).
end{cases}tag{10}$$
Taking in account $(9),$ can be written
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k-1)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-c(N-4k)^{-s}big)big(1-d(N-2k)^{-t}big)Big)\
&×Big(1-big(1-d(N-4k-2)^{-t}big)big(1-c(N-2k-1)^{-s}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}cleft(dfrac{N}{(2k-1)^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k-1}right)^{-t}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}dleft(dfrac{N}{4k^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k}right)^{-s}right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-d(N-4k)^{-t}big)big(1-(N-2k)^{-s}big)Big)\
&&Big(1-big(1-(N-4k-2)^{-s}big)big(1-d(N-2k-1)^{-t}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}dleft(dfrac{N}{(2k-1)^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k-1}right)^{-s}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}cleft(dfrac{N}{4k^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k}right)^{-t}right)right).
end{cases}tag{11}$$
Model $(11)$ should be checked theoretically and practically, but it gives the approach to the required estimations.
The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
$endgroup$
$color{brown}{textbf{HINT}}$
Denote the target sequence ${F_3(n)}$ and let us try to estimate the probability $P(N)}$ that natural number belongs to ${F_3}.$
Suppose
$$F_3(1)=1,quad F_3(2)=2,quad P(1)=P(2)=P(5) = P(6) = 1,\ P(3)=P(4)=P(7)=P(8)=0,tag1$$
$$V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(N) = left[V^{-1}(N)right].tag2$$
Let $P_a(N)$ is the probability that N does not belong to arithmetic progression and $P_g(N)$ is the similar probability for geometric progressions.
Suppose
$$P(N) = P_a(N)P_g(N)).tag3$$
$color{brown}{textbf{Arithmetic Probability estimation.}}$
Suppose
$$P_a(N)=prodlimits_{k=1}^{[N/2]}P_a(N,k),tag4$$
where $P_a(N,k)$ is the probability that arithmetic progression ${N-2k,N-k, N}$ does not exist for any $j.$
Suppose
$$P_a(N,k) = big(1-P(N-2k)big)big((1-P(N-k)big).tag5$$
$color{brown}{textbf{Geometric Probability estimation.}}$
Suppose
$$P_g(N)=prodlimits_{k=1}^{left[,sqrt Nn,right]}P_g(N,k),tag6$$
where $P_g(N,k)$ is the probability that geometric progression $left(dfrac{N}{k^2}, dfrac Nk, Nright}$ with the denominator $k$ does not exist for all $i,j.$
Taking in account that the geometric progression can exist only if $k^2,| N,$ suppose
$$P_g(N,k) = left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right).tag7$$
$color{brown}{textbf{Common model.}}$
Common model can be simplified to next one,
begin{cases}
P(N) = 1-prodlimits_{k=1}^{[N/2-1]}Big(1-big(1-P(N-2k)big)big(1-P(N-k)big)Big)\
timesprodlimits_{k=1}^{left[sqrt Nright]}left(1-left(1-dfrac1{k^2}Pleft(dfrac{N}{k^2}right)right)left(1-Pleft(dfrac{N}{k}right)right)right)\[4pt]
P(1)=P(2)=P(5) = P(6) = 1,quad P(3)=P(4)=P(7)=P(8)=0\
V(N)=sumlimits_{i=1}^{N}P(i),quad F_3(n) = left[V^{-1}(n)right].tag8
end{cases}
Looking the solution in the form of
$$left{begin{align}
&P(N)=P_v(N),quadtext{where}quad v=left[dfrac{N-1 mod 4}2right],\[4pt]
&P_0(N)=
begin{cases}
1,quadtext{if}quad N<9\
cN^{-s},quadtext{otherwise}
end{cases}\[4pt]
&P_1(N)=
begin{cases}
0,quadtext{if}quad N<9\
dN^{-t},quadtext{otherwise}
end{cases}
end{align}right.tag9$$
then
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_0(N-4k)big)big(1-P_1(N-2k)big)Big)\
&×Big(1-big(1-P_1(N-4k-2)big)big(1-P_0(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_0left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_1left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_1left(dfrac{N}{4k^2}right)right)
left(1-P_0left(dfrac{N}{2k}right)right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=1}^{[N/4-1]}Big(1-big(1-P_1(N-4k)big)big(1-P_0(N-2k)big)Big)\
&&Big(1-big(1-P_0(N-4k-2)big)big(1-P_1(N-2k-1)big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}P_1left(dfrac{N}{(2k-1)^2}right)right)
left(1-P_0left(dfrac{N}{2k-1}right)right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}P_0left(dfrac{N}{4k^2}right)right)
left(1-P_1left(dfrac{N}{2k}right)right)right).
end{cases}tag{10}$$
Taking in account $(9),$ can be written
$$begin{cases}
&P_0(N) =1-&prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k-1)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-c(N-4k)^{-s}big)big(1-d(N-2k)^{-t}big)Big)\
&×Big(1-big(1-d(N-4k-2)^{-t}big)big(1-c(N-2k-1)^{-s}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}cleft(dfrac{N}{(2k-1)^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k-1}right)^{-t}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}dleft(dfrac{N}{4k^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k}right)^{-s}right)right)\[4pt]
&P_1(N) = 1- &prodlimits_{k=[N/4-2]}^{[N/4-1]},c(N-2k)^{-s}prodlimits_{k=1}^{[N/4-3]}Big(1-big(1-d(N-4k)^{-t}big)big(1-(N-2k)^{-s}big)Big)\
&&Big(1-big(1-(N-4k-2)^{-s}big)big(1-d(N-2k-1)^{-t}big)Big)\
&×prodlimits_{k=1}^{left[sqrt N/2right]-1}
left(1-left(1-dfrac1{(2k-1)^2}dleft(dfrac{N}{(2k-1)^2}right)^{-t}right)
left(1-cleft(dfrac{N}{2k-1}right)^{-s}right)right)\[4pt]
&×left(1-left(1-dfrac1{4k^2}cleft(dfrac{N}{4k^2}right)^{-s}right)
left(1-dleft(dfrac{N}{2k}right)^{-t}right)right).
end{cases}tag{11}$$
Model $(11)$ should be checked theoretically and practically, but it gives the approach to the required estimations.
The next steps are estimation of parameters $$c,d,s,t$$ and using of obtained model.
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
edited Jan 7 at 8:16
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
answered Jan 2 at 19:52
Yuri NegometyanovYuri Negometyanov
12.8k1729
12.8k1729
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
add a comment |
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
$begingroup$
@Joseph O'Rourke Approximation can be changed, but parametrization is actual.
$endgroup$
– Yuri Negometyanov
Jan 7 at 6:55
add a comment |
$begingroup$
Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because
a paper discussing this conjecture was just published, I thought I would mention it:
Erdős Conjecture (1940s or 1950s). If $A subset mathbb{N}$
satisfies $sum_{n in A} frac{1}{n}= infty$, then
$A$ contains arbitrarily long arithmetic progressions.
In
- Grochow, Joshua. "New applications of the polynomial method: The cap
set conjecture and beyond." Bulletin of the American Mathematical
Society, Vol.56, No.1, Jan. 2019,
he says:
"It remains open even to prove that a set $A$ satisfying the hypothesis contains $3$-term arithmetic progressions."
$endgroup$
add a comment |
$begingroup$
Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because
a paper discussing this conjecture was just published, I thought I would mention it:
Erdős Conjecture (1940s or 1950s). If $A subset mathbb{N}$
satisfies $sum_{n in A} frac{1}{n}= infty$, then
$A$ contains arbitrarily long arithmetic progressions.
In
- Grochow, Joshua. "New applications of the polynomial method: The cap
set conjecture and beyond." Bulletin of the American Mathematical
Society, Vol.56, No.1, Jan. 2019,
he says:
"It remains open even to prove that a set $A$ satisfying the hypothesis contains $3$-term arithmetic progressions."
$endgroup$
add a comment |
$begingroup$
Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because
a paper discussing this conjecture was just published, I thought I would mention it:
Erdős Conjecture (1940s or 1950s). If $A subset mathbb{N}$
satisfies $sum_{n in A} frac{1}{n}= infty$, then
$A$ contains arbitrarily long arithmetic progressions.
In
- Grochow, Joshua. "New applications of the polynomial method: The cap
set conjecture and beyond." Bulletin of the American Mathematical
Society, Vol.56, No.1, Jan. 2019,
he says:
"It remains open even to prove that a set $A$ satisfying the hypothesis contains $3$-term arithmetic progressions."
$endgroup$
Since both @awwalker and @mathworker21 mentioned Erdős' conjecture, and because
a paper discussing this conjecture was just published, I thought I would mention it:
Erdős Conjecture (1940s or 1950s). If $A subset mathbb{N}$
satisfies $sum_{n in A} frac{1}{n}= infty$, then
$A$ contains arbitrarily long arithmetic progressions.
In
- Grochow, Joshua. "New applications of the polynomial method: The cap
set conjecture and beyond." Bulletin of the American Mathematical
Society, Vol.56, No.1, Jan. 2019,
he says:
"It remains open even to prove that a set $A$ satisfying the hypothesis contains $3$-term arithmetic progressions."
edited Jan 6 at 22:44
community wiki
2 revs
Joseph O'Rourke
add a comment |
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.
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%2f858918%2fa-sequence-that-avoids-both-arithmetic-and-geometric-progressions%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
6
$begingroup$
Expanding on your numerical data I conclude that Q3 can be answered in the negative. 457th term is 17933 with sum of reciprocals : 2.702607644337383 1000th term is 66102 : 2.718058753659135 but alas, somewhere shortly after that the sum excedes e. 2000 253701 2.7259164358931023. 3000 442429 2.7287027640882804.
$endgroup$
– Michael Stocker
Jul 7 '14 at 13:16
3
$begingroup$
The answer to Q2 is definitely Yes, it converges, because even just avoiding arithmetic progressions leads to convergence. Converges to what constant is unclear.
$endgroup$
– Joseph O'Rourke
Jul 9 '14 at 0:33
2
$begingroup$
@JosephO'Rourke Really? I may be ignorant here so going out on a limb, but I don't think $a_n=nln n$ is in an arithmetic progression, but the sum of its reciprocals diverges.
$endgroup$
– John Molokach
Mar 25 '16 at 2:46
1
$begingroup$
@JohnMolokach In fact, when you look at the difference in terms in the OEIS sequence, it looks a lot like OEIS A006519, which is $O(nln(n))$. The sequence talked about in the question is a bit different, but I think asymptotically they'd be the same, meaning the sum of reciprocals diverges. And of course, this is just a heuristic, not a proof.
$endgroup$
– Turambar
Apr 28 '16 at 17:52
1
$begingroup$
On the other hand, after looking at it out to $i = 10,000$, the chart of the differences doesn't seem to be as similar to A006519 as I thought. Its peaks grow faster and have a more bell curve distribution around them instead of the recursive characteristics of A006519. At $i = 10,000$, $ln(s_i)/ln(i) = 1.679258559$ and generally growing, with the sum of reciprocals around $2.734896156$. So if the "power" keeps generally growing (and doesn't start dropping to 1 after some point), then the sum is below $2.736095249$.
$endgroup$
– Turambar
May 10 '16 at 16:14