A very base-ic problem

Computer Science Level 4

Consider a sequence, where the n n -th term is the smallest positive integer such that when it is written in base k k representation, it only consists of the digits 1's and 0's, where k = 2 , 3 , … , n + 1 k = 2, 3, \ldots, n+1 .

For example, since 2 = 1 0 2 2 = 10_2 and 3 = 1 1 2 = 1 0 3 3 = 11_2 = 10_3 and 4 = 10 0 2 = 1 1 3 = 1 0 4 4 = 100_2 = 11_3 = 10_4 , hence the first three terms of the sequence is 2 , 3 , 4 2,3,4 .

What is the fourth number in this sequence? Give your answer in decimal representation.

This is not an original problem.


The answer is 82000.

View wiki
Janardhanan Sivaramakrishnan by Janardhanan Sivaramakris… , 42

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Every number, represented in base-2 would be with 1's and 0's only. Hence, it does not affect the result.

For a number to be a part of the sequence it has to be in 1's and 0's in base 3. Hence, should belong to the set { 3 , 4 , 9 , 10 , 12 , 13 , 27 , 28 , 30 , 31 , ⋯ } \{3,4,9,10,12,13,27,28,30,31,\cdots\}

To satisfy the base-4 criterion, it should also belong to the set { 4 , 5 , 16 , 17 , 20 , 21 , 64 , 65 , 68 , 69 , ⋯ } \{4,5,16,17,20,21,64,65,68,69,\cdots\}

Similarly, the 4-th term should also be in the sequence, (base-5 sequence) { 5 , 6 , 25 , 26 , 30 , 31 , 125 , 126 , 130 , ⋯ } \{5,6,25,26,30,31,125,126,130,\cdots\}

Searching for the common element gives the answer 82000 \boxed{82000}

8200 0 10 = 1010000000101000 0 2 82000_{10}=10100000001010000_{2}

= 1101111100 1 3 =11011111001_{3}

= 11000110 0 4 =110001100_4

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Here 's a C++ solution to generate the first 4 terms of the sequence defined in the problem. Runs in about 0.05 secs.

Prasun Biswas - 5 years, 9 months ago

Searching for the common element gives the answer 82000 <<<< How do you know this? By listing out those thousands of integers first?

Or a programming code?

Or you watched a Numberphile video?

Pi Han Goh - 5 years, 9 months ago

Log in to reply

Not analytical, but by programming only.

Set a estimated upper limit for T 4 T_4 (say 10000) and tried to find the intersection of the different sets. Turns out that there is only one element (less than 100000, at least), which is 82000.

Janardhanan Sivaramakrishnan - 5 years, 9 months ago

Log in to reply

The MATLAB Code : 

function S=set10(max_no,base)

n_dig = floor(log(max_no)/log(base)+1);

S=[0;1];

for i=1:(n_dig-1)

   S=[S;S+base^i];

end

S(1:2)=[];

I=find(S>max_no);

S(I)=[];

end

Janardhanan Sivaramakrishnan - 5 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...