[FIXED] Identifying pattern and code for this problem

Issue

I found this problem and I'm trying to come up with a solution for it, but I'm not getting the pattern here. Any advice on how to approach it? (I want to understand what the pattern is and a suggestion on how to approach the solution). Thanks!

---

In this problem, you are asked to implement a function pattern(k) which given an integer k ≥ 0, returns a string as shown in the below examples. Guess the pattern for k ≥ 6. You are advised to use recursion.

Test Program:

for k in range(0,6):
    print("pattern("+str(k)+"): " + pattern(k))

Output:

pattern(0): 1
pattern(1): 1
pattern(2): 1001
pattern(3): 10010001
pattern(4): 1001000100001001
pattern(5): 10010001000010010000010010001

I didn't understand the pattern to begin with it properly. Perhaps a simple explanation can allow me to write up some sample code that might work.

Solution

In recursion, a function needs a termination condition and otherwise calls itself.

The termination condition looks like: if k < 2: return '1'

Now look for recurring patterns.

• pattern 2 has at most 2 zeros
• pattern 3 has at most 3 zeros
• pattern 4 has at most 4 zeros
• pattern 5 has at most 5 zeros

It looks like '0'*k is part of the pattern.

• pattern 3 looks like it starts with pattern 2.
• pattern 4 looks like it starts with pattern 3.
• pattern 5 looks like it starts with pattern 4.

Also:

• pattern 3 ends with pattern 1
• pattern 4 ends with pattern 2
• pattern 5 ends with pattern 3

The recursive function looks like pattern(k-1) + '0'*k + pattern(k-2).

Let's try it:

def pattern(k):
    if k < 2:
        return '1'
    return pattern(k-1) + '0'*k + pattern(k-2)

for k in range(7):
    print(f'pattern({k}): {pattern(k)}')

Output:

pattern(0): 1
pattern(1): 1
pattern(2): 1001
pattern(3): 10010001
pattern(4): 1001000100001001
pattern(5): 10010001000010010000010010001
pattern(6): 100100010000100100000100100010000001001000100001001

Answered By - Mark Tolonen