Reordering N with
unique sum constraint
I was looking this
w.-e. (0ct. 3rd 2009) for a reordering of the natural numbers
obeying two conditions:
a) a maximum of a(n)'s must be equal to n
b) a(n)=n if and only if a(n) is the unique sum
of a pair of successive terms in S
I have build S(1)
and S(2); both sequences seem to
have 50% of their terms a(n) at rank n in S (they are in yellow):
S(1): 2,1,3,4,6,5,7,9,8,10,11,12,14,13,24,16,17,18,20,22,21,25,23,28,19,26,27,29,15,34,30,32,33,36,35,31,37,38,41,40,50,42,43,44,45,46,47,48,49,52,51,54,53,55,57,56,58,59,39,61,60,62,70,64,65,66,72,68,69,73,71,74,67,76,75,77,78,80,79,82,81,83,63,86,85,88,87,99,89,90,91,92,93,96,95,102,97,98,104,100...
This is to be understood like this:
“3”
is in 3rd position in S(1)
and 3 is the
only term of S(1) which can be seen as the addition of two successive terms of S(1):
3=2+1
“4”
is in 4th position in S(1)
and 4 is the only term of S(1) which can be seen as the
addition of two successive terms of S(1): 4=1+3
“7”
is in 7th position in S(1)
and 7 is the only term of S(1) which can be seen as the
addition of two successive terms of S(1): 7=3+4
“10”
is in 10th position in S(1)
and 10 is the only term of S(1) which can be seen as the addition
of two successive terms of S(1): 10=4+6
etc.
In other words: take any pair of two successive terms
in S(1) --a(k) and a(k+1)-- their sum n =
[a(k)+a(k+1)] is equal to a(n).
Example: 12+14 is 26, and 26 is at position 26 in S(1);
or take 5+7 which sum up to 12, and 12 is at position 12 in S(1).
The yellow terms are the terms where a(n) = n.
I want to maximize the quantity of yellow terms in S(1), knowing that S(1) must be a reordering of the natural
numbers.
S(2): 2,1,3,4,6,5,7,9,8,10,11,12,14,13,25,16,17,18,30,15,21,19,23,20,24,26,27,22,34,28,29,31,33,32,35,36,52,38,37,40,41,42,43,44,45,39,55,48,49,50,46,47,53,51,54,56,57,59,58,60,76,62,61,64,65,63,67,66,68,69,71,70,72,73,75,74,77,79,78,114,81,80,83,84,85,98,87,88,89,90,82,94,93,108,86,96,97,91,99,100...
S(1) was build filling the "holes" first
(with the smallest available integer)
S(2) was build placing the natural numbers first (in the
first available "hole")
Building method of S(1) (“fill the holes first”):
n = 1, 2, 3, 4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,...
S(1)= ?
Can we fill the first blank space (“hole”) with 1? No,
this would mean that a(1)=1, thus a(1) is a “yellow” term, thus 1 is the unique
sum of two successive terms of S; but this would imply the presence of 0 --
which is expressly forbidden (“natural numbers only”)
So we fill the first hole with 2 (which is indeed “the
smallest available integer”):
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2,
The next “hole” will be filled with 1, “the smallest
available integer”:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1,
As we have two successive terms, we must see if their
sum has a free spot for itself in S; yes -- 1+2 is 3 and the 3rd place
is available; we thus mark 3 in yellow:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3,
As we have now another pair of successive terms (1 and
3) we must proceed accordingly:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
And again with the new pair (3+4):
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
., ., 7,
The next hole to be filled is next to 4; can we fill it with
“5”? No, as this “5” would be in 5th position in S; this is forbidden because “5” would be
in yellow, thus, and resulting in the sum of two successive integers -- which
is now impossible. So let’s fill the hole with 6:
n = 1, 2, 3,
4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, ., 7,
... we immediately put a
yellow “10” in 10th position (as this “6” creates the new pair 4+6):
n = 1, 2, 3,
4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, ., 7, ., .,10,
The next hole is between 6 and 7; we fill it with “5”
(“smallest available integer”), creating thus two new pairs (6+5 and 5+7) which
give birth to the yellow terms 11 and 12:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, ., .,10,11,12,
But those two new yellow terms immediately produce
themselves two more yellow terms: the pair 10+11 produces yellow 21 and the
pair 11+12 produces yellow 23:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, ., .,10,11,12, ., ., ., ., ., ., .,
.,21, .,23,
The next hole is next to 7; for the same reason as
above, we must fill it with 9 (and not 8); birth of yellow 16:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9,
.,10,11,12, ., ., .,16, ., ., ., .,21, .,23,
Next hole is filled with 8; two new pairs are created
-- and two yellow results, accordingly, yellow 17 and 18:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12, ., ., .,16,17,18, ., .,21, .,23,
But 17 and 18, together with 16, produce themselves yellow
33 and 35:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12, ., ., .,16,17,18, ., .,21, .,23, ., ., ., ., ., ., .,
., .,33, .,35,
The next hole cannot be filled with 13 -- thus 14
(producing yellow 26):
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14, ., .,16,17,18, ., .,21, .,23, ., .,26, ., ., ., ., ., .,33, .,35,
The next hole is filled with 13 (“smallest... etc.”),
producing yellow 27:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14,13, .,16,17,18, ., .,21, .,23, ., .,26,27, ., ., ., ., .,33, .,35, --> 53
... and this yellow 27
produces yellow 53 (not showed here for lack of space)
Now the funny (?) part:
what comes next, after 13? Let’s call this natural number “nn”;
can “nn” be “15”? No, as this “15” would be at the 15th
place in S(1) -- which is forbidden (unless yellow
itself). Can it be “16”? No, as “16” is already used; can it be “17” or “18”?
No, for the same reason, they are already used. Could “nn”
be “19”? No, as this “19” would create two new pairs and two new yellow terms:
13+19(=32) and 19+16(=35); we would accept “nn”=“19”
if both spots were free (both 32 and 35) -- but this is not the case [32 is
free but 35 is occupied by the yellow term 35 (resulting in the former addition
17+18)]. We must then try “nn”=“20” -- but “20”+13
gives 33, and the spot 33 is already occupied; what about “21”, then? No, “21”
is already used; then “22”? No, “22”+13 gives 35 and the spot 35 is occupied,
as we’ve seen; could “nn”=“23”? No, “23” has been
used already -- what about “nn”=”24”? Yes, we have a
hit, “24” produces the new pairs (and yellow terms) 13+24(=37) and 24+16(=40):
n = 1, 2, 3,
4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,
S(1)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14,13,24,16,17,18, ., .,21, .,23, ., .,26,27, ., ., ., ., .,33, .,35, .,37, ., .,40,
etc.
This method produces a new term of S at each step.
The other method [“place the natural numbers first (in
the first available "hole")”] is based exactly on the same principle,
except that the main concern, here, is to place the naturals, one after the
other -- and not filling the holes, one after the other, as before.
The building steps of S(2)
are:
n = 1, 2, 3,
4, 5, 6, 7, 8,
9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,...
S(2)= ., 1,
S(2)= 2, 1,
S(2)= 2, 1, 3,
S(2)= 2, 1, 3, 4,
S(2)= 2, 1, 3, 4,
., ., 7,
S(2)= 2, 1, 3, 4,
., 5, 7,
S(2)= 2, 1, 3, 4,
., 5, 7, ., ., .,
.,12,
S(2)= 2, 1, 3, 4,
6, 5, 7, .,
., ., .,12,
S(2)= 2, 1, 3, 4,
6, 5, 7, ., .,10,11,12,
S(2)= 2, 1, 3, 4,
6, 5, 7, ., .,10,11,12, ., ., ., ., ., ., .,
.,21, .,23,
S(2)= 2, 1, 3, 4,
6, 5, 7, ., 8,10,11,12, ., ., ., ., ., ., .,
.,21, .,23,
S(2)= 2, 1, 3, 4,
6, 5, 7, ., 8,10,11,12, ., ., ., ., .,18, ., .,21, .,23,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9,
8,10,11,12, ., ., ., ., .,18, ., .,21, .,23,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12, ., ., .,16,17,18, ., .,21, .,23,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12, ., ., .,16,17,18, ., .,21, .,23, ., ., ., ., ., ., .,
., .,33, .,35,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12, .,13, .,16,17,18, ., .,21, .,23, ., ., ., ., ., ., .,
., .,33, .,35,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14,13, .,16,17,18, ., .,21, .,23, ., ., ., ., ., ., .,
., .,33, .,35,
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14,13, .,16,17,18, ., .,21, .,23, ., .,26,27, ., ., ., ., .,33, .,35, --> 53
S(2)= 2, 1, 3, 4,
6, 5, 7, 9, 8,10,11,12,14,13, .,16,17,18, .,15,21, .,23, ., .,26,27, ., ., ., ., .,33, .,35, --> 53
... this is where the results of methods S(1) and S(2)
start to diverge: the spot occupied by “15” in S(2) is occupied by “22” in S(1).
Let’s compare the first 40 terms of S(1),
S(2) and underline the differences:
S(1)= 2,1,3,4,6,5,7,9,8,10,11,12,14,13,24,16,17,18,20,22,21,25,23,28,19,26,27,29,15,34,30,32,33,36,35,31,37,38,41,40,
S(2)= 2,1,3,4,6,5,7,9,8,10,11,12,14,13,25,16,17,18,30,15,21,19,23,20,24,26,27,22,34,28,29,31,33,32,35,36,52,38,37,40,
Two different methods -- but the ratio “yellow
terms/terms of S” seems to be constant and equal to 50%.
Is there an S(3) sequence
somewhere beating this ratio?
Best,
É.
Main page here (in french)