8
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ If it's as manay "3 digit" numbers as possible, then I don't think your first 5 terms are in the sequence $\endgroup$ – AHKieran Jan 15 at 8:53
  • $\begingroup$ @AHKieran Yes, but they just need to be padded on the left with zeroes (the range in the question is 001 to 360). $\endgroup$ – Jaap Scherphuis Jan 15 at 9:01
  • $\begingroup$ @JaapScherphuis Oh right I see. In the examples they limited it to 2 digits and then only used 2 digits so I thought that was the case. Forgot that that was because they couldn't repeat numbers. $\endgroup$ – AHKieran Jan 15 at 10:05
  • $\begingroup$ This looks like an outstanding approach! Tomorrow I'll comment more -- I will wait a day in case anyone else wants to post an answer. Thanks! $\endgroup$ – James Waldby - jwpat7 Jan 15 at 19:38
  • $\begingroup$ This is optimal. As you showed, the factors must be two separate increasing sequences of primes. To have an entry with 11 values, both sequences would need to have 6 primes, which would mean the 11th value would have to be at least 481. $\endgroup$ – user3294068 Jan 16 at 20:18
0
$\begingroup$

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.3C)/35000 seconds on a 3.40GHz Intel i5-7500, ie search time grows exponentially with chain length.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Using your notation above, wouldn't this be a valid solution to the problem with length 12, 2 longer than the current solution: [(3,2),(2,5),(5,3),(3,7),(7,5),(5,11),(11,7),(7,13),(13,11),(11,17),(17,13),(13,19)] $\endgroup$ – Justin Heath Jan 17 at 17:22
  • $\begingroup$ @JustinHeath, that's not a valid sequence per the problem description, which says, "... whenever a prime divides some number in the combination, then it divides exactly two consecutive numbers ... or it only divides the first number, or only divides the last number." Your suggested sequence uses each of 3, 5, 7, 11, and 13 more than twice. $\endgroup$ – James Waldby - jwpat7 Jan 17 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.