Number Discrimination

Number Theory Level 5

Let a 1 , a 2 , a 3 , a 4 , … a_1, a_2, a_3, a_4, \ldots be a sequence of all positive integers arranged in ascending order that have the following properties:

  • It is not a multiple of 5.
  • It does not contain the digit 1.

Here are the first few terms in this sequence: 2 , 3 , 4 , 6 , 7 , 8 , 9 , 22 , 23 , 24 , 26 , 27 , … 2,\,3,\,4,\,6,\,7,\,8,\,9,\,22,\,23,\,24,\,26,\,27,\,\ldots Find the value of a 1153 . a_{1153}.

See also:


The answer is 3037.

Kenneth Tan by Kenneth Tan , 21, Malaysia

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

Kenneth Tan
Jun 30, 2018

We can't use the digit 1 1 ?! That means we can only use the digits 0 0 , 2 2 , 3 3 , 4 4 , 5 5 , 6 6 , 7 7 , 8 8 and 9 9 , except in the units place which is even worse, we can't even use the digits 0 0 and 5 5 , since the number cannot be a multiple of 5 (see divisibility rules )!

That leaves us with 7 digits left to work with in the units place and 9 digits to work with for the rest, this suggests us to think the number in the units place in base 7 and the rest in base 9 .

To start, given a number a n a_n from the sequence, let's separate the units digit of a n a_n from the other digits, let's call the units digit "quasi-seconds" and the remaining digits "quasi-minutes" (lousy name I know, but bear with me).

Let's now remap the digits of quasi-seconds using this mapping list: 2 → 0 3 → 1 4 → 2 6 → 3 7 → 4 8 → 5 9 → 6 \begin{aligned} 2&\rightarrow0 \\ 3&\rightarrow1 \\ 4&\rightarrow2 \\ 6&\rightarrow3 \\ 7&\rightarrow4 \\ 8&\rightarrow5 \\ 9&\rightarrow6 \end{aligned}

And remap the digits of quasi-minutes using this mapping list: 0 → 0 2 → 1 3 → 2 4 → 3 5 → 4 6 → 5 7 → 6 8 → 7 9 → 8 \begin{aligned} 0&\rightarrow0 \\ 2&\rightarrow1 \\ 3&\rightarrow2 \\ 4&\rightarrow3 \\ 5&\rightarrow4 \\ 6&\rightarrow5 \\ 7&\rightarrow6 \\ 8&\rightarrow7 \\ 9&\rightarrow8 \end{aligned}

Notice that after the remapping, the number in quasi-seconds functions just like an ordinary number in base 7 (since we only use the digits from 0 0 to 6 6 ), and the number in quasi-minutes functions just like an ordinary number in base 9 (since we only use the digits from 0 0 to 8 8 ). Furthermore, just like when measuring time where 60 60 seconds equals 1 1 minute, 7 7 quasi-seconds equals 1 1 quasi-minute .

Awesome, we shall now write the remapped numbers in the form [ quasi-minutes ] 9 ′ [ quasi-seconds ] 7 ′ ′ [\text{quasi-minutes}]_9'\,[\text{quasi-seconds}]_7'' to represent the original number (the subscript numbers represents its base).

For example, if a n = 23059 a_n=23059 , then it is remapped and rewritten as 120 4 9 ′ 6 7 ′ ′ 1204_9'\,6_7'' , and since we can treat 120 4 9 1204_9 and 6 7 6_7 as ordinary numbers in their respective bases, we can do some conversions: 120 4 9 1204_9 is 895 895 in base 10, thus 120 4 9 ′ 6 7 ′ ′ = 89 5 10 ′ 6 7 ′ ′ = ( 895 × 7 + 6 ) 10 ′ ′ = 627 1 10 ′ ′ 1204_9'\,6_7''=895_{10}'\,6_7''=(895\times7+6)_{10}''=6271_{10}'' .

What could we do with these remappings and conversions you might ask? Let's remap the first several terms of the sequence and see what we can find:

n a n After remapping and rewriting Equivalent quasi-seconds in base 10 1 2 0 9 ′ 0 7 ′ ′ 0 10 ′ ′ 2 3 0 9 ′ 1 7 ′ ′ 1 10 ′ ′ 3 4 0 9 ′ 2 7 ′ ′ 2 10 ′ ′ 4 6 0 9 ′ 3 7 ′ ′ 3 10 ′ ′ 5 7 0 9 ′ 4 7 ′ ′ 4 10 ′ ′ 6 8 0 9 ′ 5 7 ′ ′ 5 10 ′ ′ 7 9 0 9 ′ 6 7 ′ ′ 6 10 ′ ′ 8 22 1 9 ′ 0 7 ′ ′ 7 10 ′ ′ 9 23 1 9 ′ 1 7 ′ ′ 8 10 ′ ′ 10 24 1 9 ′ 2 7 ′ ′ 9 10 ′ ′ 11 26 1 9 ′ 3 7 ′ ′ 1 0 10 ′ ′ 12 27 1 9 ′ 4 7 ′ ′ 1 1 10 ′ ′ 13 28 1 9 ′ 5 7 ′ ′ 1 2 10 ′ ′ 14 29 1 9 ′ 6 7 ′ ′ 1 3 10 ′ ′ 15 32 2 9 ′ 0 7 ′ ′ 1 4 10 ′ ′ \begin{array}{|c|c|c|c|} \hline \\ n & a_n & \text{After remapping and rewriting} & \text{Equivalent quasi-seconds in base 10} \\ \hline 1 & 2 & 0_9'\,0_7'' & 0_{10}'' \\ \hline 2 & 3 & 0_9'\,1_7'' & 1_{10}'' \\ \hline 3 & 4 & 0_9'\,2_7'' & 2_{10}'' \\ \hline 4 & 6 & 0_9'\,3_7'' & 3_{10}'' \\ \hline 5 & 7 & 0_9'\,4_7'' & 4_{10}'' \\ \hline 6 & 8 & 0_9'\,5_7'' & 5_{10}'' \\ \hline 7 & 9 & 0_9'\,6_7'' & 6_{10}'' \\ \hline 8 & 22 & 1_9'\,0_7'' & 7_{10}'' \\ \hline 9 & 23 & 1_9'\,1_7'' & 8_{10}'' \\ \hline 10 & 24 & 1_9'\,2_7'' & 9_{10}'' \\ \hline 11 & 26 & 1_9'\,3_7'' & 10_{10}'' \\ \hline 12 & 27 & 1_9'\,4_7'' & 11_{10}'' \\ \hline 13 & 28 & 1_9'\,5_7'' & 12_{10}'' \\ \hline 14 & 29 & 1_9'\,6_7'' & 13_{10}'' \\ \hline 15 & 32 & 2_9'\,0_7'' & 14_{10}'' \\ \hline \end{array}

Marvelous! We have now established a pattern:

When a n a_n is remapped and rewritten, its equivalent number of quasi-seconds must be equal to ( n − 1 ) 10 ′ ′ (n-1)_{10}''

To figure out a 1153 a_{1153} , all we need now is to work backwards.

When a 1153 a_{1153} is remapped and rewritten, its equivalent number of quasi-seconds is 115 2 10 ′ ′ 1152_{10}'' . Because 1152 = 164 × 7 + 4 1152=164\times7+4 and 164 164 is 20 2 9 202_9 in base 9, ∴ 115 2 10 ′ ′ = 20 2 9 ′ 4 7 ′ ′ \therefore 1152_{10}''=202_9'\,4_7''

We now need to undo the mappings of 20 2 9 ′ 4 7 ′ ′ 202_9'\,4_7'' (use the mapping lists above with the arrows reversed): 20 2 9 ′ 4 7 ′ ′ → 3037 202_9'\,4_7''\rightarrow3037

Therefore, a 1153 = 3037 a_{1153}=3037 .

3 Helpful 0 Interesting 0 Brilliant 0 Confused

My solution as under.
0000 t o 0009 , 0002 , 0003 , 0004 , 0006 , 0007 , 0008 , 0009 , a 1 t o a 7 0010 t o 0019 , 0012 , 0013 , 0014 , 0016 , 0017 , 0018 , 0019 , X X X X 0020 t o 0029 , 0022 , 0023 , 0024 , 0026 , 0027 , 0028 , 0029 , a 8 t o a 14 0030 t o 0039 , 0032 , t o 0039 , a 15 t o a 21 0040 t o 0049 , 0042 , t o 0049 , a 22 t o a 28 0050 t o 0059 , 0052 , t o 0059 , a 29 t o a 35 0060 t o 0069 , 0062 , t o 0069 , a 36 t o a 42 0070 t o 0079 , 0072 , t o 0079 , a 43 t o a 49 0080 t o 0089 , 0082 , t o 0089 , a 50 t o a 56 0090 t o 0099 , 0092 , 0093 , 0094 , 0096 , 0097 , 0098 , 0099 , a 57 t o a 63 \color{#3D99F6}{ \begin{aligned} \\ 0000~~~~to~~~~0009,&~~~~~~0002,&~0003,~0004,~0006,~0007,~0008,~~~&0009,&~~~~~~~&a_{~1}~~~~to~~a_7\\ 0010~~~~to~~~~0019,&~~~~~~0012,&~0013,~0014,~0016,~0017,~0018,~~~&0019,&~~~~~~~XXXX\\ 0020~~~~to~~~~0029,&~~~~~~0022,&~0023,~0024,~0026,~0027,~0028,~~~&0029,&~~~~~~~~&a_{~8}~~~~to~~a_{14}\\ 0030~~~~to~~~~0039,&~~~~~~0032,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0039,&~~~~~~~&a_{15}~~to~~a_{21}\\ 0040~~~~to~~~~0049,&~~~~~~0042,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0049,&~~~~~~~&a_{22}~~to~~a_{28}\\ 0050~~~~to~~~~0059,&~~~~~~0052,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0059,&~~~~~~~&a_{29}~~to~~a_{35}\\ 0060~~~~to~~~~0069,&~~~~~~0062,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0069,&~~~~~~~&a_{36}~~to~~a_{42}\\ 0070~~~~to~~~~0079,&~~~~~~0072,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0079,&~~~~~~~&a_{43}~~to~~a_{49}\\ 0080~~~~to~~~~0089,&~~~~~~0082,&to~~~~~~~~~~~~~~~~~~~~~~~~~~~~&0089,&~~~~~~~&a_{50}~~to~~a_{56}\\ 0090~~~~to~~~~0099,&~~~~~~0092,&~0093,~0094,~0096,~0097,~0098,~~~&0099,&~~~~~~~&a_{57}~~to~~a_{63} \\ \end{aligned} } \\
∴ 0000 t o 0099 ⟹ a 1 t o a 63 . ∴ 0100 t o 0199 ⟹ X X X X ∴ 0200 t o 0299 ⟹ a 64 t o a 126 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ∴ 0800 t o 0899 ⟹ a 441 t o a 503 . ∴ 0900 t o 0999 ⟹ a 504 t o a 567 . \color{#E81990}{ \begin{aligned} \\ \therefore~~0000~~to~~0099~~~&\implies~~a_1 &~~~~~~to~~~a_{63}.\\ \therefore~~0100~~to~~0199~~~&\implies~~XXXX\\ \therefore~~0200~~to~~0299~~~&\implies~~a_{64} &~~to~~~a_{126}.\\ ..........&..........\\ ........&..........\\ \therefore~~0800~~to~~0899~~~&\implies~~a_{441} &~~~to~~~a_{503}.\\ \therefore~~0900~~to~~0999~~~&\implies~~a_{504}&~~~to~~~a_{567}.\\ \end{aligned} } \\

∴ 0000 t o 0999 ⟹ a 1 t o a 567 . ∴ 1000 t o 1999 ⟹ X X X X . ∴ 2000 t o 2999 ⟹ a 568 t o a 1134 . \color{#BA33D6}{ \begin{aligned} \\ \therefore~~0000~~to~~0999~~~&\implies~~a_1 &~~~~~~to~~~a_{567}.\\ \therefore~~1000~~to~~1999~~~&\implies~~XXXX&~~~~~~~~~.\\ \therefore~~2000~~to~~2999~~~&\implies~~a_{568} &~~~~~~to~~~a_{1134}.\\ \end{aligned} } \\

S o 1153 − 1134 = 19 . ∴ 19 f r o m 3000 a r e . 1 4 t h o f 3000 , i s 3029 = a 1134 + 14 . 19 − 14 = 5 l e f t f r o m 3030 t o 3039 a r e : 3032 , 3033 , 3034 , 3036 , 3037. \color{#20A900}{ \\ So~1153-1134=19~.\\ \therefore~~19~from ~3000 ~are. \\ 14^{th} ~~of~3000,~ is~3029=a_{1134+14}.\\ 19-14=5~~left~ from ~3030~to~3039~are: \\ 3032,~3033,~3034,~3036,~3037. } \\

∴ a 1153 = 3037. \therefore~~a_{1153} = \Huge \color{#D61F06}{3037}.\\

In a thousand there are 7 * 9 *9=567 "a"s. I took 7 * 8 * 8=448, since I took all numbers with 5 on places
other than the unit place also out of "a" .

Niranjan Khanderia - 2 years, 10 months ago

Log in to reply

The solution above is detail explanation for ease of understanding. Below a short solution, same logic.
From given condition, the unit digit of "a"' has "seven" options, 2,3,4,6,7,8,9.
Since only "1" can not appear in "a", the tenth, hundredth, and thousands, digits have 10-1=9 options.
So from 0000 to 0999 will have 7 * 9 * 9=567 "a"s.
So from 1000 to 1999 will have no "a"s, because of 1 .
So from 2000 to 2999 will have 7 * 9 * 9=567 more "a"s.
So from 0000 to 2999 we will have 567+567=1143 "a"s.
i m p l i e s a 1143 = 2999 implies~a_{1143}=2999 .
We need 1153 - 1143=19 more "a"s, coming from 3000.......
From 3000-3009-seven, 3010-3019-none, 3020-3029- seven more, 3030-3039-more seven.
So from 3000-3039 we will have 7 * 3=21 "a"s. But we need only 19.
Eliminating last two numbers from 3000-3039, that is 3039 and 3038,
we get a 1153 = 3037. a_{1153}=\color{#D61F06}{3037}.

Niranjan Khanderia - 2 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...