[seqfan] Powers of 2 jump paths through array

Ron Hardin rhhardin at att.net
Sun Nov 29 14:30:29 CET 2015


Put 0 at the upper left and n*k-1 at the lower right and ask how many ways to fill the array with values differing by a power of two (so every path from NW to SE has to be jumps of powers of 2).  One with powers of 3.

The curiosity is 0 (no solutions) values except at the obvious n=2 k=2 with diagonal neighbors, particularly in the last (/tmp/fiz)

/tmp/fit
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal and vertical neighbors by a power of two
Table starts
......1..........1..............1................2................16
......1..........4.............21..............139..............8463
......1.........21...........2024...........170970...........7796840
......2........139.........170970.........36765048.......19256175024
.....16.......8463........7796840......19256175024....62221755947285
.....79.....219995.....1346956387....7187180809683.29140746691543180
....456....6639203...226158945148.2362949716450873..................
...2194..149441692.16064538255326...................................
..20801.6260685646..................................................
.142675.............................................................

Some solutions for n=3 k=3
..0..2..3....0..4..0....0..2..3....0..2..0....0..4..0....0..4..5....0..1..0
..2..3..4....2..3..4....4..6..4....4..0..4....1..5..4....1..2..6....4..0..4
..6..4..8....6..4..8....2..4..8....2..4..8....3..7..8....5..4..8....0..4..8

/tmp/fiu
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal and vertical neighbors by a power of THREE
Table starts
....1.........1...............1..................4....................12
....1.........0..............16..................0..................1958
....1........16.............114..............17740................959210
....4.........0...........17740..................0.............361386063
...12......1958..........959210..........361386063..........112968132978
...32.........0........30623109..................0........64809856589464
..109....654833......1704484254......7949178726430.....84621589234807688
..366.........0.....71709918479..................0.151566698900534826760
.1189.112227310...2699912810448.453490948990318650......................
.9855.........0.303524301107151.........................................

Some solutions for n=3 k=3
..0..3..6....0..3..4....0..3..4....0..3..6....0..1..2....0..3..2....0..1..2
..1..4..5....1..4..7....3..4..7....3..2..5....1..2..5....3..4..5....3..4..5
..4..7..8....2..5..8....4..7..8....6..5..8....4..5..8....4..5..8....2..5..8

/tmp/fiv
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal and antidiagonal neighbors by a power of two
Table starts
.......1...........1..............1...............2...............16
.......1...........2.............84............1354............38791
.......3..........79...........9327..........927797.........82725668
......16........2194........1427680.......505822314.....376251416588
.....125......142675......308395359....807767184602.2435259956770588
....1296.....7604426....99770416100.938564405271330.................
...16807...451816635.38840832559548.................................
..262144.25239520503................................................
.4782969............................................................

Some solutions for n=3 k=3
..0..2..6....0..1..2....0..4..8....0..2..3....0..4..5....0..2..6....0..4..8
..3..4..8....5..4..0....2..4..6....3..1..5....8..6..7....3..4..2....5..6..5
..8..0..8....2..4..8....0..4..8....5..7..8....5..6..8....5..6..8....4..6..8

/tmp/fiw
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal, vertical and antidiagonal neighbors by a power of two
Table starts
......1......1.........1............2.............16............79
......1......2.........4............8............166...........257
......1......4.........0..........177...........2228.............0
......2......8.......177.........2908..........35824........572832
.....16....166......2228........35824.......11746590......19502116
.....79....257.........0.......572832.......19502116.............0
....456...1627....534268.....19333806.....7124418191..108447811968
...2194..19283...1808623....160881658....64498108909.4758708947913
..20801..90682.........0...5664401710.19456105428825.............0
.142675.542663.221771015.229732307880.61995422081770..............

Some solutions for n=4 k=3
..0..4..8....0..4..8....0..4..5....0..4..8....0..4..2....0..4..8....0..4..2
..8..6..7....8..6.10....2..6..7....8..6.10....8..6.10....8..6..7....2..6..4
..4..8..9....4..8..9...10..8..9...10..8..9....4..8..9....7..5..3....4..5..3
..6..7.11....6..7.11....9..7.11....6..7.11....6..7.11....6..7.11....6..7.11

/tmp/fix
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal, diagonal and antidiagonal neighbors by a power of two
Table starts
.......1.........1............1............2.............16...........79
.......1.........0...........64..........559..........10444.......154825
.......3........21.........2660........85492........2331618....206993090
......16.......585........35328......2723409.....1299561587.361488020990
.....125......8463......5852058...3979565339.25336433674079.............
....1296....294394....962138367.796308532514............................
...16807...6639203.498846580538.........................................
..262144.120126908......................................................
.4782969................................................................

Some solutions for n=3 k=3
..0..4..6....0..4..3....0..4..3....0..4..0....0..1..2....0..1..3....0..4..8
..5..4..5....6..4..3....8..4..5....6..4..8....5..4..5....2..4..0....2..4..2
..2..6..8....3..4..8....2..6..8....5..7..8....8..7..8....6..4..8....0..4..8

/tmp/fiy
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal and diagonal neighbors by a power of two
Table starts
......1.........1...........1............2...............16.............79
......1.........0..........64..........908............29296.........538517
......3........45........5625.......392320.........13534874.....3413887598
.....16......1098......545952.....36820624......41288839953.26221405955605
....125.....86800...147336019.283374980138.1819521260530360...............
...1296...3882992.54825790582.............................................
..16807.199692576.........................................................
.262144...................................................................

Some solutions for n=3 k=3
..0..8..4....0..1..3....0..8..6....0..4..5....0..4..8....0..2..4....0..4..3
..0..4..6....8..4..5....5..4..6....8..4..2....3..4..6....5..4..0....3..4..2
..2..4..8....6..7..8....3..7..8....7..6..8....3..4..8....8..7..8....6..7..8

/tmp/fiz
T(n,k)=Number of nXk 0..n*k-1 arrays with upper left zero and lower right n*k-1 and each element differing from its horizontal, vertical and diagonal neighbors by a power of two
Table starts
......1......1........1.........2........16........79.......456.....2194
......1......0........0........12.........0.........0......1030........0
......1......0.......36.........0.........0......2506....294152........0
......2.....12........0.........0.........0......3249....595253.11022848
.....16......0........0.........0.........0.........0.949287922........0
.....79......0.....2506......3249.........0...7928582.223328748........0
....456...1030...294152....595253.949287922.223328748...................
...2194......0........0..11022848.........0.............................
..20801......0.19516777.504744595.......................................
.142675.298764.83909226.................................................

Some solutions for n=3 k=3
..0..8..4....0..2..1....0..2..1....0..2..4....0..2..1....0..2..4....0..8..4
..8..4..0....2..4..0....8..4..0....2..4..0....8..4..0....2..4..6....8..4..6
..4..6..8....1..0..8....4..6..8....4..6..8....7..6..8....4..0..8....4..6..8
 rhhardin at mindspring.com rhhardin at att.net (either)



More information about the SeqFan mailing list