[seqfan] Re: Number names - a chain

[Sean A. Irvine]

My exhaustive search for the number name problem completed. The
longest solutions contain 25 numbers, the first solution is:

8, 4, 7, 30, 1, 36, 11, 40, 9, 42, 6, 0, 56, 100, 60, 101, 66, 111,
50, 700, 52, 707, 2, 5, 2000

A total of 14442624 solutions of length 25 were found, subject to the
equivalences identified by Hans.  That is, the total number of
solutions would be higher since it is possible to substitute other
values for the end-points in some cases.

It is, of course, possible to play this game with any word list.

For days:

1: Monday

For months:

8: December, August, November, July, March, June, May, October

For Greek letters:

22: chi, tau, epsilon, gamma, phi, zeta, nu, sigma, rho, kappa, xi,
omega, psi, delta, pi, theta, omicron, eta, upsilon, beta, mu, iota

(might not be longest possible)

For chemical elements:

30: thallium, neon, lithium, carbon, thulium, boron, hassium, krypton,
helium, argon, lutetium, radon, bismuth, copper, gallium, xenon,
yttrium, lead, phosphorus, zinc, sulphur, tin, mercury, gold, rhenium,
cobalt, iridium, oxygen, calcium, hydrogen

(might not be longest possible)

Fundamentally these problems involve trying to finding the longest
Hamiltonian path in a graph. This problem is NP-hard, so there is no
known efficient way of solving this problem for an arbitrary list.


Sean.

On 10 March 2015 at 19:06, Hans Havermann <gladhobo at teksavvy.com> wrote:
> Sean A. Irvine: "Still running, but I've found one of length 17 so far."
>
> SeqFan dealt with the subject on the 6th & 7th of July, 2011. At the time Douglas McNeil suggested 5, 2, 9, 40, 11, 36, 1, 30, 7, 44, 6, 12, 4, 66, 101, 56, 100, 50, 0, 60, 104, which I told him could be preceded by 2000 (for a total length of 22). In posing the query, Eric Angelini had come up with a 15-element chain compared to the 13 he submitted this time around. ;)
>
> I did set up a brute force attack in a private email to Eric Angelini, Douglas McNeil, Claudio Meller, and Maximilian Hasler which is worth repeating if anyone wants to have a go at it:
>
> "While I suggested that there were 181 numbers in the connectible (at least one neighbour) universe, 144 of these have only one neighbour and, to the extent that these necessarily represent chain end-points, 137 of them may be culled in favour of a representative from their seven (2, 3, 4, 5, 6, 11, 50) sinks. Thus,
>
> 500 will represent any of {505, 506, 507, 509, 511, 600, 605, 606, 607, 609, 611, 705, 706, 709, 900, 905, 906, 907, 909, 911}
>
> 6000000 will represent any of {6000006, 6000000000, 6000000006, 6006000000, 6006000006, 6000000000000000000000000000000, 6000000000000000000000000000006, 6000000000000000000000006000000, 6000000000000000000000006000006, 6000000000000000000006000000000, 6000000000000000000006000000006, 6000000000000000000006006000000, 6000000000000000000006006000006}
>
> 8 will represent any of {16, 17, 18, 19, 26, 27, 28, 29, 67, 68, 69, 70, 76, 77, 78, 79, 80, 86, 87, 88, 89, 90, 96, 97, 98, 99}
>
> 2000 will represent {2002}
>
> 14 will represent any of {21, 22, 23, 24, 41, 43, 102, 103, 110, 112, 114, 120, 121, 122, 123, 124, 140, 141, 142, 143, 144, 200, 201, 202, 203, 204, 210, 211, 212, 214, 220, 221, 222, 223, 224, 240, 241, 242, 243, 244, 300, 301, 302, 303, 304, 310, 311, 312, 314, 320, 321, 322, 323, 324, 340, 341, 342, 343, 344, 402, 403, 410, 412, 414, 420, 421, 422, 423, 424, 440, 441, 442, 443, 444}
>
> 46 will represent either of {62, 64}
>
> 107 will represent {701}
>
>
> This cull leaves us with just 44 numbers:
>
> {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 20, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 66, 100, 101, 104, 107, 111, 400, 401, 404, 411, 500, 700, 707, 711, 2000, 6000000}
>
> ... with the following corresponding sets of neighbours:
>
> {{6, 50, 56, 60, 66}, {6, 30, 36, 50, 56, 60, 66}, {5, 6, 7, 9, 11, 500, 700, 707, 711}, {6, 6000000}, {6, 7, 8, 9, 10, 11, 12, 20, 60, 66}, {2, 2000}, {0, 1, 2, 3, 4, 10, 11, 12, 14, 20, 40, 42, 44, 100, 101, 104, 111, 400, 401, 404, 411}, {2, 4, 30, 32, 34, 40, 42, 44, 50, 52, 54}, {4}, {2, 4, 40, 42, 44}, {4, 6}, {2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 66}, {4, 6}, {6}, {4, 6}, {1, 7, 11}, {7, 11}, {7, 11}, {1, 11}, {6, 7, 9, 11}, {6, 7, 9, 11}, {6, 7, 9, 11}, {11}, {0, 1, 7, 11, 100, 101, 107, 111, 700, 707, 711}, {7, 11, 700, 707, 711}, {7, 11}, {0, 1, 11, 100, 101, 111}, {0, 1, 4, 11, 100, 101, 104, 111, 400, 401, 404, 411}, {0, 1, 4, 11, 100, 101, 104, 111, 400, 401, 404, 411}, {6, 50, 56, 60, 66}, {6, 50, 56, 60, 66}, {6, 60, 66}, {50}, {6, 50, 56, 60, 66}, {6, 60, 66}, {6, 60, 66}, {6, 60, 66}, {6, 60, 66}, {2}, {2, 50, 52}, {2, 50, 52}, {2, 50, 52}, {5}, {3}}"
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/