Can you open a safe with a lengthy complicated combination?

Question

Two cousins were talking about their parents' safes. "They said I can keep my comic books in their safe, if I figure out the right combination, and enter it on the keypad correctly on my first attempt," said the first cousin. "I've listed out a lot of combinations but haven't figured out if I have the right one."

"How will you know when it's right, anyway? Did they tell you some formula for the combination?" asked the second cousin.

"Yes, they said the combination has as many 3-digit numbers as possible in the range from 001 to 360, if the numbers only get bigger as the combination goes along, and if all the numbers are squarefree semiprimes with their factors uniquely chained together."

"That sounds pretty complicated! Can you give me an example of some numbers that could appear in a combination like that on a smaller range?"

"Sure. Say that only two-digit numbers in the range 1 to 36 are allowed. I figure that the sequence (10, 14, 21, 33), or (5x2, 2x7, 7x3, 3x11), is the answer."

"So, 'uniquely chained' means that whenever a prime divides some number in the combination, then it divides exactly two consecutive numbers?"

"Yes, or it only divides the first number, or only divides the last number. Like 5 and 11 in that example."

"Oh, right. ... What would the answer be if only two-digit numbers in the range 01 to 90 are allowed?"

"I figured that one out too. It's (14, 22, 33, 39, 65, 85), or (7x2, 2x11, 11x3, 3x13, 13x5, 5x17)."

"Ok, now let me think for a minute about that 1 to 360 combination ... Ok, it might take me a couple of minutes ..."

While the second cousin is thinking, can you figure out the answer?

Answer 1

I think it's a safe assumption that the answer will be of the form:

a*2, 2*b, b*3, 3*c, c*5, 5*d, where a < b < c < d ... are the smallest "remaining primes" (2, 3, 5... are already used).

The reasoning is that

We get to use all the smallest primes as many times as possible. Using higher primes serves no purpose.

Now, we want to get the longest sequence. To achieve this

we can just try using different values for a, and fill in the sequence:

For instance, if we try

a=17, we'll get: 17*2, 2*19, 19*3, 3*23, 23*5, 5*29, 29*7, 7*31, 31*11. Here we see that the prime 13 is not used. So, this is likely not optimal.

Let's try another:

If we start at a=13, we'll get [13*2, 2*17, 17*3, 3*19, 19*5, 5*23, 23*7, 7*29, 29*11, 11*31, which is one number higher. Now, every prime between 2 and 31 is used, and the highest product 11*31 is 341, just slightly lower than 360.

Going even lower is not an alternative, since:

All the primes between 2 and 31 are used in the sequence above. If we start with a = 11, we'll get: 11*2, 2*13, 13*3, 3*17, 17*5, 5*19, 19*7, 7*23, and then 23*29>360 since 11 is already used.

Without a rigorous proof I'm going to say the combination is:

26, 34, 51, 57, 95, 115, 161, 203, 319, 341

Answer 2

CG has a correct and accepted answer, as verified by a python program I wrote that generates all possible chains over the range 001...360.

Shown below are examples of solutions for other ranges of numbers, in a form that shows chain length, the chain's maximum value, and solution(s).

C2  10  [(2, 3), (2, 5)]

C3  21  [(2, 5), (2, 7), (3, 7)]
C3  21  [(2, 5), (5, 3), (3, 7)]

C4  33  [(2, 5), (2, 7), (3, 7), (3, 11)]

C5  65  [(2, 7), (2, 11), (3, 11), (3, 13), (5, 13)]
C5  65  [(2, 7), (7, 3), (3, 11), (11, 5), (5, 13)]

C6  85  [(2, 7), (2, 11), (3, 11), (3, 13), (5, 13), (5, 17)]

C7  133 [(2, 11), (2, 13), (3, 13), (3, 17), (5, 17), (5, 19), (7, 19)]
C7  133 [(2, 11), (11, 3), (3, 13), (13, 5), (5, 17), (17, 7), (7, 19)]

C8  161 [(2, 11), (2, 13), (3, 13), (3, 17), (5, 17), (5, 19), (7, 19), (7, 23)]

In the examples above, when numbers up to 21, 65, or 133 are allowed, there is not a unique solution, and two different patterns appear. There are unique solutions when numbers up to 10, 33, 85, or 161 are allowed. Existence of limits that lead to one solution when the longest chain length is even, and two solutions when it's odd, is true among all cases looked at so far, ie up to length 20. In the two-solution cases, one of them follows the pattern that CG identifies, and the other follows a different pattern.

The python program takes about 4 milliseconds to generate all possible chains for the examples above, but takes almost 4 minutes to test all possible chains for cases up to length 20. For length C, it takes around (2.3^C)/35000 seconds on a 3.40GHz Intel i5-7500, ie search time grows exponentially with chain length.