Graph-Maker-Other
view release on metacpan or search on metacpan
devel/Hanoi-config-sequence.gp view on Meta::CPAN
\\-----------------------------------------------------------------------------
\\ Hamiltonian Path - 3-Valuation Moves
\\ A128173 Numbers in ternary reflected Gray code order.
\\ A128173 ,0,1,2,5,4,3,6,7,8
\\ apply(to_ternary,OEIS_data("A128173"))
\\ Refs in Hinz et al book:
\\ [290] Scorer, Grundy, Smith, "Some Binary Games", Mathematics Magazine 280
\\ (1944) 96103. Page 99 brief
\\ [204] X. Lu, "Towers of Hanoi Graphs", International Journal of Computer
\\ Mathematics 19 (1986) 2338.
\\ vector(20,n,valuation(n,3))
\\ A007949 Greatest k such that 3^k divides n. Or, 3-adic valuation of n.
\\ A007949 ,0,0,1,0,0,1,0,0,2,0
Hamiltonian_step(v,n) =
{
my(d=valuation(n,3)+1);
while(#v<d,v=concat(v,[0]));
my(from=v[d],to);
to=from + (-1)^vecsum(v[d+1..#v]);
for(i=1,d-1,
if(v[i]==from||v[i]==to,error(v" move d="d" from="from" to="to)));
v[d] = to;
v;
}
{
if(0,
my(v=[],seen=Map(),S=List([]));
for(n=1,20,
v=Hamiltonian_step(v,n);
printf("%2d %s moved %d\n", n, v, valuation(n,3)+1);
my(s=fromdigits(apply(t->if(t==0,0,t), Vecrev(v)),3));
s=to_ternary(s);
listput(S,s);
);
print(S);
quit);
}
\\-----------------------------------------------------------------------------
\\ A055662 configs of optimal paths, in decimal digits starting from 1
\\ ternary digit k = which spindle number holds a disc
\\
\\ 0,1, 21,22, 122,120,110,111, 2111,2112,2102,2100,2200,2201,2221,2222
\\
\\ low digit: 0, 1, 1, 2, 2, 0
\\ 2nd digit: 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0
\\ 6 periodic, 12 periodic, etc 6*2^k, opposite ways
\\ 0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0,0, 1, 1, 2, 2, 0
\\ A131555
\\ not in OEIS: 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0,0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0,0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0
\\ vector(20,n,n--; A055662(n)%10)
\\ vector(20,n,n--; A055662(n)\10%10)
\\ vector(20,n,n--; A055662(n)\100%10)
\\ formula in A055662
A055662(n) =
{
n>=0 || error();
sum(j=0,if(n,logint(n,2)),
10^j * (floor((n/2^j + 1)/2)*(-1)^j % 3));
}
{
OEIS_check_func("A055662");
}
\\
\\ x x x . x x
\\ +1
\\ |floor
\\ vector(20,n,hammingweight(n)%2)
{
check_equal(vector(20,k, (2^k)%3),
vector(20,k, k%2 + 1));
check_equal(vector(3^5,n,n--; A055662(n)%10),
vector(3^5,n,n--; [0,1,1,2,2,0][n%6+1]),
"A055662 low digit 6-periodic");
}
{
my(n=from_binary(1111000111));
check_equal(A055662(n), 2222000111);
}
{
if(0,
print(concat(vector(12,n, digits(A055662(n)))));
print(concat(vector(12,n, Vecrev(digits(A055662(n))))));
quit);
\\ not in OEIS: 1,2,1,2,2,1,2,2,1,2,0,1,1,0,1,1,1,2,1,1,1,2,1,1,2,2,1,0,2,2,1,0,0,2,2,0,0
\\ not in OEIS: 1,1,2,2,2,2,2,1,0,2,1,0,1,1,1,1,1,1,1,1,2,2,1,1,2,2,0,1,2,0,0,1,2,0,0,2,2
}
\\-----------------------------------------------------------------------------
\\ discs on spindles by runs
\\ 1, 1, 2, 1
\\ discs 5 4 2,3 1 4 prefer occupied
\\ peg X Y X
bit_runs(n) =
{
my(v=binary(n),pos=0,prev=0);
for(i=1,#v, if(v[i]==prev, v[pos]++, prev=v[i];pos++;v[pos]=1));
v[1..pos];
}
check_equal(bit_runs(0), []);
check_equal(bit_runs(22), [1,1,2,1]);
check_equal(bit_runs(from_binary(110000101)), [2,4,1,1,1]);
other_pegs(peg) = setminus([1,2,3],[peg]);
other1(peg) = other_pegs(peg)[1];
other2(peg) = other_pegs(peg)[2];
pegallocs(runs) =
{
my(ret=vector(vecsum(runs)),
devel/Hanoi-config-sequence.gp view on Meta::CPAN
check_equal(vector(1024,n, A060571(n)),
vector(1024,n, (-A060571(2*n))%3),
"A060571 source, by A060571(2n)");
\\ digit of configuration
check_equal(vector(1024,n, A060571(n)),
vector(1024,n, extract_digit(A055662(n-1), valuation(n,2))),
"A060571 source, by digit of configuration");
}
\\-----------------------------------------------------------------------------
\\ A060572 destination of n'th move
\\ my line of code in A060572
A060572(n) = (- (-1)^valuation(n,2) - n)%3;
{
OEIS_check_func("A060572");
}
extract_digit(n,p) = (n\10^p)%10;
{
\\ Donald Sampson in A060572, a(2n) with 1<->2 reversed
check_equal(vector(1024,n, A060572(n)),
vector(1024,n, (-A060572(2*n))%3),
"A060572 destination, by A060572(2n)");
\\ digit of configuration
check_equal(vector(1024,n, A060572(n)),
vector(1024,n, extract_digit(A055662(n), valuation(n,2))),
"A060572 destination, by digit of configuration");
check_equal(vector(1024,n, A060572(n)),
vector(1024,n, (A060571(n) - (-1)^A001511(n)) % 3),
"A060572 destination related to source");
check_equal(A060572(1), 1, "2^k even to peg 1");
check_equal(vector(64,k,k--; A060572(2^k)),
vector(64,k,k--; if(k%2==0,1,2)),
"A060572 n=2^k move of largest disc to target 2,1");
my(a=A060572);
\\ Donald Sampson in A060572
check_equal(vector(1024,n, a(2*n)),
vector(1024,n, (-a(n))%3),
"A060572(2n) by reversal");
check_equal(vector(1024,n, a(n)),
vector(1024,n, my(p=2^A001511(n));
if(n>p, (a(n-p) - (-1)^A001511(n)) % 3,
( - (-1)^A001511(n)) % 3)),
"A060572 destination recurrence");
\\ c = A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k.
check_equal(vector(124,n, a(n)),
vector(124,n, my(ret=0,c=0);
while(1, my(p=2^A001511(n)); c++;
ret += -(-1)^A001511(n); if(n>p,n-=p,break));
ret%3),
"A060572 destination quotient, counting one by one");
\\ first formula in A060572
check_equal(vector(1024,n, a(n)),
vector(1024,n, (A060571(n) - (-1)^A001511(n)) % 3),
"A060572 destination related to source");
\\ Donald Sampson in A060572
check_equal(vector(1024,n, a(5*n)),
vector(1024,n, (-A060571(n))%3),
"A060572(5n) by source reversed");
}
\\-----------------------------------------------------------------------------
\\ A055661 ternary first move peg 1
A055661(n) = from_ternary(A055662(n));
{
OEIS_check_func("A055662");
check_equal(A055661(0), 0);
check_equal(A055661(1), 1, "A055661 first move to peg 1");
}
\\-----------------------------------------------------------------------------
\\ A128202 ternary first move peg 2
A128202(n) =
{
my(v=binary(bitxor(n,n>>1)),s=(-1)^#v,d=0); for(i=1,#v, if(v[i],d=(d+s)%3,s=-s); v[i]=d); fromdigits(v,3);
}
{
my(want=[0, 2, 5, 4, 22, 21, 24, 26]);
check_equal(vector(#want,n,n--; A128202(n)), want,
"A128202 Sunic samples");
}
{
\\ OEIS_check_func("A128202");
}
{
check_equal(A128202(0), 0);
check_equal(A128202(1), 2);
check_equal(vector(3^8,n,n--; A128202(n)),
vector(3^8,n,n--; A004488(A055661(n))),
"A128202 samples");
my(n=from_binary(111000011100011));
check_equal(n,28899);
check_equal(A128202(n), 14086228);
check_equal(to_binary(n), 111000011100011);
check_equal(to_ternary(A128202(n)), 222111122200011);
}
{
\\ DATA section
if(0,
for(n=0,55,print1(A128202(n),",");if(n==21||n==38,print()));
print();
quit);
my(want=[
0,2,5,4,22,21,24,26,53,52,46,45,36,38,41,40,202,201,204,206,197,196,
190,189,216,218,221,220,238,237,240,242,485,484,478,477,468,470,473,
472,418,417,420,422,413,412,406,405,324,326,329,328,346,345,348,350
( run in 2.258 seconds using v1.01-cache-2.11-cpan-39bf76dae61 )