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?
This builds the strings of digits recursively:
clearvars,clc
global ns ct
ns=''; ct=zeros(1,20);
addon
fprintf('%d,',ct)
fprintf('\n')
function addon()
global ns ct
for new=['1' '2']
ok=true;
if length(ns)>0
if ns(end)==new && new=='1'
ok=false;
end
if length(ns)>1 && new=='2'
if isequal(ns(end-1:end),'22')
ok=false;
end
end
end
if ok
ns=[ns new];
ct(length(ns))=ct(length(ns))+1;
disp(ns)
if length(ns)<20
addon
end
ns=ns(1:end-1);
end
end
end
finds
2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200,265,351,465
for length 1 through 20 respectively.
Sloane's OEIS identifiest this as A000931 Padovan sequence (or Padovan numbers): a(n) = a(n-2) + a(n-3) with a(0) = 1, a(1) = a(2) = 0.
and several other series with different offsets from the beginning.
|
|
Posted by Charlie
on 2024-07-07 09:15:52 |
computer solution
