How many n digit numbers you can write by using only 1's and 2's and you are allowed to use neither two consecutive 1's nor three consecutive 2's?
Algorithm: Start with all binary numbers. Since all binary numbers begin with '1', also include binary numbers with a single '0' prepended. Now eliminate any with two consecutive 0's or three consecutive 1's. Next inflate each digit by 1, so you have 1s and 2s instead of 0s and 1s.
Make a dictionary where the keys are the number of digits in a given 1-2 number, and the values are lists of valid 1-2 numbers of that particular number of digits.
Finally print out the list keys and the associated number of 'key'-digit numbers are in that key's value, ie list.
But since trial and error shows that the final key in the dictionary most likely will have a value which is an incomplete list, discard the final key:value pair of the dictionary.
Output: (zero based)
[1, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465]
There is 1 way to have zero digits: nothing
2 ways to have 1 digit: 1, 2
3 ways to have 2 digits: 12, 22, 21
4 ways to have 3 digits: 121, 122, 221, 212
This is in Sloane's oeis:
A164001 Spiral of triangles around a hexagon.
---------------
d = {}
for n in range(0,2**20):
b1 = bin(n)[2:]
if '111' in b1:
continue
if '00' in b1:
continue
b0 = '0' + b1
b0 = b0.replace('1', '2')
b1 = b1.replace('1', '2')
b0 = b0.replace('0', '1')
b1 = b1.replace('0', '1')
if n == 0:
b0 = ''
b1 = '1'
len0 = len(b0)
len1 = len(b1)
if len0 not in d.keys():
d[len0] = []
if len1 not in d.keys():
d[len1] = []
d[len0].append(b0)
d[len1].append(b1)
dcounts = {}
for k,v in d.items():
dcounts[k] = len(v)
print(list(dcounts.values())[:-1])
|
|
Posted by Larry
on 2024-07-07 08:23:32 |
Computer Solution
