Re: Rearrangements of 1,2,...,N

On 14 Feb., 15:40, "jhni...@xxxxxxxxx" <jhni...@xxxxxxxxx> wrote:
On 14 feb, 10:34, Tim Little <t...@xxxxxxxxxxxxxxxxxx> wrote:

On 2009-02-14, Roman B. Binder <rbin...@xxxxxxxxxxxxxxxx> wrote:

On Feb 14, 2009 Jos[] H. Nieto wrote:
Is it always possible to rearrange the positive integers from 1 to N
in such a way that the sums of consecutive terms are prime numbers?
[...]
Your question applies for string or ring of such numbers ?

Odd and even positions must alternate, so for a ring structure any odd
N fails.

For a sequence, it seems very likely that a suitable arrangement is
always possible but I do not have a proof.

- Tim

I am interested in sequences. So far I know that, if 2n-1 and 2n+1 are
twin primes, then the integers from 1 to 2n may be arranged as:

2n, 1, 2n-2, 3, 2n-4, 5,..., 4, 2n-3, 2, 2n-1

with alternate prime sums 2n+1 and 2n-1.

jhn


As long as one finds enough prime twind, the following
"proof by induction works":

Pseudo theorem:
For all n in N, n>1, there is a permutation a_1, a_2, ..., a_n
of 1,2,...,n such that such that all consecutive sums a_i + a_{i+1}
are prime and a_n = n.
Pseudo proof:
Small n are easy: n=2: 1,2. n=3: 1,2,3.
Assume n>3 and n+k-1, n+k+1 are twin primes for some k<n
By induction hypothesis, find a permutation b_1, ..., b_k of
1,...,k with b_k=k and b_i+b_{i+1} prime for all i.
Then
b_1, ..., b_k=k, n-1, k+2, n-3, k+4, ..., k+5, n-4, k+3, n-2,k+1, n
is as requested (note that n=k mod 2 so the pattern matches correctly)

However, can we always find twin primes n <= p < p+2 <= 2n+1?
Since we don't even know if there are infinitely twin primes at all,
this is not very encouraging.
(How far do we get numerically with this? It is, what is the
smallest n such that [n,2n+1] contains no twin primes?)

..-.-.

As far from a proof as possible, but heuristically, let's assume
the consecutive sums are random numbers between 3 and 2n-1, inclusive
(actually, a random permutation would prefer sums near n+1).
Each is prime with probability ~1/ln(n), thus allare prime with
probability ~1/(ln(n))^n so that it is very likely that at least
one of the n!~(n/e)^n possible arrangements succeeWrite down the
sequence ds...
.

Relevant Pages

  • Re: Rearrangements of 1,2,...,N
    ... in such a way that the sums of consecutive terms are prime numbers? ... we need not prepend anything (and the sequence is ... Since we don't even know if there are infinitely twin primes at all, ... probability ~1/)^n so that it is very likely that at least ...
    (sci.math)
  • Rearrangements of 1,2,...,N
    ... Is it always possible to rearrange the positive integers from 1 to N ... in such a way that the sums of consecutive terms are prime numbers? ...
    (sci.math)
  • Quantum Gravity 343.3: MIT and National Security Agency USA Explore Sums and Differences and Their S
    ... Yufei Zhao of MIT in "Subsets ... characterized by the number of missing sums and differences," arXiv: ... The size of S resembles a binomial probability distribution. ... Interactions and also to the 5th Interaction of Repulsion and the fact ...
    (sci.physics)
  • Re: Dice Program
    ... dont create a new object every time method is called. ... Having two dice with 6 sides how do you get ... I can find ONLY 21 different combinations and ONLY 11 different sums. ... probability of any particular sum is 1 in 11. ...
    (comp.lang.java.help)
  • Re: Probability question
    ... What is the probability that the sum of the two dice is the same on ... (some sums appear more than once to make points all equally likely). ... this is the probability of the same outcome on both rolls. ...
    (sci.math)