In the sequence formed by concatenating the digits 1, 2, 3, ..., i, i+1, ..., n what is the first appearance of k repetitions of the same digit?
For example, when k=3 the answer is:
11, 12: 111 (3 1s in a row).
Show with the same format for k = 2, 4, 5.
How far can you go?
Is there a pattern?
Note: k means "exactly k", so for k=2, the answer is not 11 because the next digit is another 1.
clearvars
countIDs=[]; begins=[]; ends = [];
s='1'; b=1;e=1;
for n=2:9999999
if n==89
xx=99;
end
ns=num2str(n);
if ns(1)==s(end)
e=n;
repd=true;
for i=1:length(ns)
if ns(i)~=ns(1)
repd=false;
break
end
end
if repd
s=[s ns];
else
s=[s ns(1:i-1)];
occurs=0;
for i=length(s):-1:1
if s(i)==s(end)
occurs=occurs+1;
else
break
end
end
if ~ismember(occurs,countIDs)
countIDs(end+1)=occurs;
begins(end+1)=b;
ends(end+1)=e;
disp([b,e,occurs])
end
b=n;
s=ns(i:end);
end
else
occurs=0; e=n-1;
for i=length(s):-1:1
if s(i)==s(end)
occurs=occurs+1;
else
break
end
end
if ~ismember(occurs,countIDs)
countIDs(end+1)=occurs;
begins(end+1)=b;
ends(end+1)=e;
disp([b,e,occurs])
end
b=n; e=n;
s=ns;
end
end
countIDs=countIDs';
[countIDs,idx]=sort(countIDs);
begins=begins(idx)';
ends=ends(idx)';
rpt=[begins,ends,countIDs];
for i=1:length(rpt)
s=num2str(rpt(i,2));
sr=repmat(s(1),1,rpt(i,3));
fprintf('%7d, %7d: %s (%d %s''s in a row)\n', ...
rpt(i,1:2),sr,rpt(i,3),sr(1))
end
1, 1: 1 (1 1's in a row)
89, 90: 99 (2 9's in a row)
11, 12: 111 (3 1's in a row)
9899, 9900: 9999 (4 9's in a row)
111, 112: 11111 (5 1's in a row)
989999, 990000: 999999 (6 9's in a row)
1111, 1112: 1111111 (7 1's in a row)
11111, 11112: 111111111 (9 1's in a row)
111111, 111112: 11111111111 (11 1's in a row)
1111111, 1111112: 1111111111111 (13 1's in a row)
There are two patterns, one for even-length sequences and one for odd-length sequences.
The first member of the even sequence is actually a bit of a unique case as 89 lacks an initial 9 before the 8 that comes before n-2 repetions, and 90 has only one 9 before a bunch of zeros.
The first member of the odd sequence is also irregular in that it only has one member, 1. The rest have two members: a sequence of (n-1)/2 + 1 1's, and a sequence of (n-1)/2 1's and a 2.
I'm sure the values for 8, 10, and 12 follow the rules and are missing as the required numbers lie beyond the bound of the searched range.
|
|
Posted by Charlie
on 2025-06-02 15:02:36 |
solution
