5
\$\begingroup\$

I am trying to solve Euler project problem 277 using python 3.8. First, I will show my program and than ask specific questions for enhancements.

The problem is a modified version of Collatz sequence. The general rule of the new one is:

  • \$ a_{n+1} = \, \,\, \frac {a_n} 3 \quad\$ if \$ a_n \$ is divisible by 3. We shall denote this as a large downward step, "D".

  • \$ a_{n+1} = \frac {4 a_n+2} 3 \, \, \$ if \$ a_n \$ divided by 3 gives a remainder of \$ 1 \$ . We shall denote this as an upward step, "U".

  • \$ a_{n+1} = \frac {2 a_n -1} 3 \, \, \$ if \$ a_n \$ divided by 3 gives a remainder of \$ 2 \$ . We shall denote this as a small downward step, "d".

For instance if \$ a_1=231\$ , then the sequence \$ \{a_n\}=\{231,77,51,17,11,7,10,14,9,3,1\} \$ corresponds to the steps "DdDddUUdDD".

The problem asks What is the smallest \$ a_1 > 10^{15}\$ that begins with the sequence "UDDDUdddDDUDDddDdDddDDUDDdUUDd"?

My code:

def modifCollatz(x, seq, num):
   if num == 0:
       return seq

   if x % 3 == 0:
       num -= 1
       x = x / 3
       seq.append("D")
       return modifCollatz(x, seq, num)

   elif x % 3 == 1:
       num -= 1
       x = (4 * x + 2) / 3
       seq.append("U")
       return modifCollatz(x, seq, num)

   else:
       x = (2 * x - 1) / 3
       num -= 1
       seq.append("d")
       return modifCollatz(x, seq, num)


wordList = []
for i in "UDDDUdddDDUDDddDdDddDDUDDdUUDd":
   wordList.append(i)

n = 10 ** 15
while True:
   if modifCollatz(n, [], 30)[0:30] == wordList:
       print(n)
       break
   else:
       n += 3
  1. That works. I have tested using the example given in problem 277.

  2. I am aware that it's using brute force and don't know what can be done to improve efficiency. I was just able to think of adding solely finding the first 30 elements of each number and incrementing by 3 n += 3, which are probably the easiest ones. What can be done additionally?

\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

Creating a list out of a string

wordList = []
for i in "UDDDUdddDDUDDddDdDddDDUDDdUUDd":
   wordList.append(i)

can be shortened to:

wordList = list("UDDDUdddDDUDDddDdDddDDUDDdUUDd")

Algorithm

The first idea is to check the sequence letter by letter. This is more efficient than generating the sequence for a number x and then see if it matches the target sequence.

To find the number that matches Dd starting from 3, it would be:

  • x = 3
  • 3 % 3 == 0, so it matches D
  • x = 3 / 3 = 1
  • 1 doesn't match d, so try next number
  • x = 3 + 1 = 4
  • 4 doesn't match D
  • x = 4 + 1 = 5
  • 5 doesn't match D
  • x = 5 + 1 = 6
  • 6 matches D
  • x = 6 / 3 = 2
  • 2 matches d
  • Solution is 6

Second idea is to filter out numbers that cannot be part of the solution. In the previous example, numbers 4 and 5 can be filtered out. Similarly to your n += 3. Let's see some examples:

Numbers that match the prefix D:

3,6,9,12,15,18,21...

Numbers that match the prefix DD:

9,18,27,36...

Numbers that match the prefix DDD:

27,54,81,...
  1. Each sequence is a subset of the previous.
  2. Numbers in the sequence differ by \$3^i\$, with i starting from 1.

Numbers that match the prefix U:

4,7,10,13,16,19,21,...

Numbers that match the prefix UU:

7,16,25,34,...

Numbers that match the prefix UUU:

25,52,79,...
  1. Each sequence is a subset of the previous.
  2. Numbers in the sequence differ by \$3^i\$, with i starting from 1.

Same for sequences that match d. Let's see a mixed prefix.

Numbers that match the prefix D:

3,6,9,12,15,18,21...

Numbers that match the prefix DU:

12,21,30,...
  1. Each sequence is a subset of the previous.
  2. Numbers in the sequence differ by \$3^i\$, with i starting from 1.
\$\endgroup\$
1
\$\begingroup\$

You're right that the brute-force algorithm is inefficient. This is a common theme of Project Euler; you're expected to use your mathematical insight to come up with more efficient algorithms.

In this case, you have already observed that once you have a correct first step, the next number with the same first step is 3 greater. You just need to extend the same thinking to numbers with the first two steps and beyond. Since all the given steps involve dividing by 3, it's easy to see that for each step, we need to examine the residue modulo 3, and if incorrect, add the appropriate multiple of 3ⁿ to the starting value to make that step correct.

(If the divisors were not all 3, then the value to add at each step would be the product of all the divisors in sequence prior to that step.)

The modified algorithm scales linearly with the length of the string, rather than exponentially as the trial-and-error method does.

\$\endgroup\$
1
  • \$\begingroup\$ I realized that thank you. After several steps, one can increment by almost one million in each while loop, which is still slow but far better. \$\endgroup\$ May 16, 2021 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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