New topic: duplication of substrings

[N. J. A. Sloane]

%I A137695
%S A137695 1, 3, 3, 7, 5, 5, 15, 9, 7, 7, 31, 13, 11, 9, 9, 63, 17,
15, 13, 11, 11, 127, 25, 19, 17, 15, 13, 13, 255, 33, 23, 21, 19, 17,
15, 15, 511, 41, 27, 25, 23, 21,
 19, 17, 17, 1023, 49, 31, 29, 27, 25, 23, 21, 19, 19, 2047, 65, 39,
33, 31, 29, 27, 25, 23, 21, 21, 4095, 81, 47, 37, 35, 33, 31, 29, 27,
25, 23, 23, 8191, 97, 55, 41, 39,
 37, 35, 33, 31, 29, 27, 25, 25, 16383, 113, 63, 45, 43, 41, 39, 37,
35, 33, 31, 29, 27, 27, 32767, 129, 71, 49, 47, 45, 43, 41, 39, 37,
35, 33, 31, 29, 29
%N A137695 Tower of Hanoi with p pegs: Number of moves needed for n
disks, using Frame's or Stewart's algorithm (formatted as upper right
triangle)
%C A137695 In the cited paper by Klavzar et al. it is proved that
Frame's algorithm and Stewart's algorithm, as well as several
variations, all yield the same number of minimal moves for the n disk,
p peg problem, given by the formula for X(n,p).
%C A137695 This sequence lists the elements of the upper right
triangle of the matrix having as rows the number of moves required,
depending on the number of disks, for a given number of pegs. (The 1st
row refers to 3 pegs, etc.)
The lower left triangle of the matrix is uninteresting, since all
elements below a given diagonal element are equal to that element,
namely 2n-1. (For p>n, each disk can be moved to a separate peg.)
%H A137695 S. Klavzar et al., <a
href="http://citeseer.ist.psu.edu/klavzar00framestewart.html">Discrete
Applied Mathematics 120 (2002) 141–157</a>, and references therein.
%F A137695 X(n,p) = sum( t=0,s-1,
2^t*binomial(p-3+t,p-3))+2^s*(n-binomial(p-3+s,p-2))
where s = max { k in Z | n > binomial(p-3+k,p-2) }
%e A137695 The complete matrix would read
%e A137695 (1st row: 3 pegs, A000225; 2nd row: 4 pegs, A007664; 3rd
row: 5 pegs, A007665.)
%e A137695 [1 3 7 15 31 63 127 255 511 1023 ...]
%e A137695 [1 3 5 9 13 17 25 33 41 49 ...]
%e A137695 [1 3 5 7 11 15 19 23 27 31 ...]
%e A137695 [1 3 5 7 9 13 17 21 25 29 ...]
%e A137695 [1 3 5 7 9 11 15 19 23 27 ...]
%e A137695 [1 3 5 7 9 11 13 17 21 25 ...]
%e A137695 [1 3 5 7 9 11 13 15 19 23 ...]
%e A137695 [1 3 5 7 9 11 13 15 17 21 ...]
%e A137695 [1 3 5 7 9 11 13 15 17 19 ...]
%o A137695 (PARI) X(n,p)={local(s=1,t=0); while(
n>binomial(p-2+t++,p-2), s+=2^t*binomial(p-3+t,p-3));
s+2^t*(n-binomial(p-3+t,p-2))}
%o A137695 A137695(n)=X(t=1+sqrtint(2*n-2-sqrtint(2*n-2)),2+n-t*(t-1)/2)
%Y A137695 Cf. A000225, A007664, A007665.
%O A137695 1
%K A137695 ,easy,nice,nonn,tabl,
%A A137695 Maximilian F. Hasler (Maximilian.Hasler at gmail.com), Feb 09 2008