Recursively Rotated Possible Permutation
Leroy Quet
%S A000001 1,3,4,2,7,8,6,11,12
%N A000001 Start with positive integers. On m_th step shift terms
a(m+1)
to a(2m-1) one position to the left, move a(m) to position (2m-1).
Sequence is limit of reordering.
%e A000001 [1,2,3,4,5,6,...]->[1,3,2,4,5,6,...]->[1,3,4,5,2,6,...]
->[1,3,4,2,6,7,...]->[1,3,4,2,7,5,...]->[1,3,4,2,7,8,...]
->...
%O A000001 1
%K A000001 ,more,nonn,
Is it a permutation of the positive integers?
(Or do some integers get rotated out to infinity?)
I bet there is a simple, even trivial, way to express which integer is
at
any particular position. (But a maybe not.)
Hugo Pfoertner has noted that the sequence follows an interesting
period-15 pattern when the terms are taken mod10.
Maybe other such patterns exist for other mod's and other
period-lengths.
thanks,
Leroy Quet
Hugo Pfoertner
A few more terms of the sequence:
( http://www.research.att.com/projects/OEIS?Anum=A098003 )
1 3 4
2 7 8
6 11 12
9 15 16
5 19 20
14 23 24
17 27 28
13 31 32
22 35 36
25 39 40
18 43 44
30 47 48
33 51 52
10 55 56
38 59 60
41 63 64
29 67 68
46 71 72
49 75 76
34 79 80
54 83 84
57 87 88
26 91 92
62 95 96
65 99 100
45 103 104
70 107 108
73 111 112
50 115 116
78 119 120
Hugo
KRamsay
Leroy Quet wrote:
| I submitted the following sequence to the EIS yesterday.
|
| %S A000001 1,3,4,2,7,8,6,11,12
| %N A000001 Start with positive integers. On m_th step shift terms
| a(m+1)
| to a(2m-1) one position to the left, move a(m) to position (2m-1).
| Sequence is limit of reordering.
| %e A000001 [1,2,3,4,5,6,...]->[1,3,2,4,5,6,...]->[1,3,4,5,2,6,...]
| ->[1,3,4,2,6,7,...]->[1,3,4,2,7,5,...]->[1,3,4,2,7,8,...]
| ->...
| %O A000001 1
| %K A000001 ,more,nonn,
|
| Is it a permutation of the positive integers?
| (Or do some integers get rotated out to infinity?)
It's a permutation.
| I bet there is a simple, even trivial, way to express which integer is
| at
| any particular position. (But a maybe not.)
I think it helps to consider what happens to the number that gets
rotated to position 2m-1 at step m. If m is odd, after (m-1)/2
further steps, it arrives at (3m-1)/2; on step (3m+1)/2 and further
ones, of course it stays where it is.
If m is even, after m/2 - 1 further steps it arrives at position 3m/2.
But then on step 3m/2 it gets rotated out again.
So for the numbers that get moved forward, the sequence of steps on
which they get moved forward can be obtained by multiplying by 3/2
over and over until the step number is odd. Then the position it
arrives at is (3m-1)/2 where m is the number of the last step on
which the number was moved to the right.
There is a one-to-one correspondence between positive integers that
are not divisible by 3, and positive integers that are not divisible
by 2. The limiting permutation is sort of a disguised version of that
transformation, with some mappings between congruence classes that
turn it into an actual permutation.
The numbers n that are congruent to 0 and 3 mod 4 are the ones that
aren't ever moved to the right. If n=4k, on step 2k+1 moves n to the
left, and n keeps moving to the left until it reaches position 3k on
step 3k, where it stops. Similarly, if n=4k+3, on step 2k it starts
shifting to the left and arrives at 3k+2 where it stops. This
accounts for the simple behavior of the second and third columns
in Hugh Pfoertner's table below. The first column is where the more
complicated behavior comes in.
In article <4140A7B0...@abouthugo.de>, Hugo Pfoertner
The numbers n of the form 4k+1 arrive at position 3k+1 after step 3k.
Then on step 3k+1 they are moved to the right. The numbers n of the
form 4k+2 arrive at position 3k+2 after step 3k+1, and then are
moved to the right on step 3k+2. We are in effect first mapping the
congruence class 4k+1 to the congruence class 3k+1 and the
congruence class 4k+2 to the congruence class 3k+2. That takes them
to the numbers that aren't divisible by 3.
Then repeatedly multiply by 3/2 until the result is odd. This could
be described as replacing the power of 2 in the number by a power
of 3.
Finally, we have to fit the odd numbers into the congruence class
3k+1, which we do by replacing m with (3m-1)/2.
To illustrate this, take the entries in the left column of Hugo
Pfoertner's table, and replace the numbers of the form 4k+1 and 4k+2
with 3k+1 and 3k+2 respectively. Then add a column with the odd
numbers in order. As you can see, the number in the first column
below is the corresponding odd number with its power of 3 replaced
by a power of 2:
1 1
2 3
5 5
7 7
4 9
11 11
13 13
10 15
17 17
19 19
14 21
23 23
25 25
8 27
29 29
31 31
22 33
35 35
37 37
26 39
41 41
43 43
20 45
47 47
49 49
34 51
53 53
55 55
38 57
59 59
Keith Ramsay
yae...@gmail.com
Have a look at the graphs for 10000 terms of https://oeis.org/A098003/graph and of its inverse permutation https://oeis.org/A098046/graph
Hugo Pfoertner