## Three’s a crowd

Posted by Chris on May 28, 2010 – 9:18 pm

What is the smallest integer that ends with a 3 and that when that 3 is moved from the end to the beginning, makes the number 3 times as large.

i.e. I want something like 312 = 3*123 (which obviously doesn’t work).

May 29th, 2010 at 12:36 am

103503 x 3 = 310509

That’s if I understood the question right…

May 29th, 2010 at 12:38 am

which I haven’t….

May 29th, 2010 at 8:40 am

No your right, just flip it around:

310509 = 3*103503

May 29th, 2010 at 12:51 pm

Nope. That doesn’t satisfy the requirement. You can’t just bung a 9 on the end. Starting with 103503, moving the 3 to the front gives 310350. But 3*103503 ≠ 310350.

May 29th, 2010 at 2:16 pm

Hints:

You will not get this using brute force.

There are a lot of digits in the number.

You will find Fermat’s little theorem very helpful.

May 29th, 2010 at 11:55 pm

103448273

is pretty dang close

but to get exactly 3, but I think I see a pattern.

May 29th, 2010 at 11:58 pm

With additional digits you can get closer and closer

13 31 2.38461538461538

103 310 3.00970873786408

1033 3103 3.00387221684414

10333 31033 3.00329042872351

10343 31034 3.00048341873731

103433 310343 3.00042539615017

103443 310344 3.00014500739538

103453 310345 2.99986467284661

1034443 3103444 3.00011117093934

1034453 3103445 3.00008313572487

1034463 3103446 3.00005510105243

1034473 3103447 3.000027066922

1034483 3103448 2.99999903333356

103448243 310344824 3.00000091833363

103448253 310344825 3.00000063800014

103448263 310344826 3.00000035766671

103448273 310344827 3.00000007733334

May 30th, 2010 at 12:05 am

I was thinking maybe this site would accept extra spaces.

I posted 3 columns.

The first line says 13 switched gives 31, which is 2.38… times 13. Each line gets closer and closer to 3

May 30th, 2010 at 2:15 am

Hi Ragknot. You’ve got the the first 8 digits of the number. Remember it’s an integer (ending with 3), so you don’t need to post the decimal fraction part.

As you’ve had a serious go, I’ll let you know that the number is 28 digits long. That craziness is why I like this problem. A very similar problem attracted me to ToM in the first place.

This site accepts the hard space: 0xA0 in charmap. <- see

May 30th, 2010 at 2:16 am

1 2 3

May 30th, 2010 at 2:48 am

I just proved it was 28 digits long. (Right when Chris wrote that message.)

Forst, I tried to find a 3 digit long which could work (abc) refers to a*100+b*10+c

We are looking for a number (ab3) such that:

3*(ab3)=(3ab)

Expand :

290a+29b=291.

29(10a+b)=291

That would mean that 29 divides 291, which obviously doesn’t.

We also see that with n numbers, we always have something like that :

29(10^n *a(0) + 10^(n-1) *a(1)… 10*a(n-1) +a(n) ) = 29…{(n-1) nines}…1

Then there would be a solution when our 29…91 can be divided by 29.

29…91 can be written : 3*10^n -9 = 3(10^n -3)

While the number we are looking for has (n+2) digits.

And when (n+2) = 28, n = 26,

if (10^n -3) = 0[29]

10^n = 3 [29]

10^(n+2) = 1 [29]

Fermat Theorem, n+2 = 28 is the only good solution.

Therefore we have a 28 digits number.

May 30th, 2010 at 3:54 am

Hi Karys. That’s more like it . You’ll find it easier to state the problem as 3*(N:3) = 3:N where N is a string (of n digits). n will turn out to be 27. You do not need to break N into n separate digits.

As you’re so close, I won’t post my solution yet.

May 30th, 2010 at 7:10 am

Here goes,

3 * 10^n + x = 3 * (x*10 + 3) —–(1)

29x = 3 * 10^n – 9

0 = 3 * 10^n – 9 (mod 29)

10^n = 3 (mod 29)

10^(n+1) = 1 (mod 29)

From Fermat’s little theorem, which states that a^(p-1) = 1 (mod p) for any prime p, we get:

n+1 = 29 – 1 = 28

thus, n = 27.

Substituting in (1), and solving for x, we get that x = 103448275862068965517241379.

Alternatively, one could use a routine like follows:

x = zeros(1,10000); len = numel(x);

m = 3; x(len) = m;

n = 0;

c = 0;

for i=len:-1:2

p = x(i) * m + c;

if (p == m && c == 0)

n = len – i +1;

break;

end

x(i-1) = mod(p, 10);

c = floor(p / 10);

end

It has been so long since I used modular arithmetic, though it can be easily guessed once primes pop in into the equation. Keep it up, folks.

May 30th, 2010 at 8:20 am

3*(N:3)=3:N

30N+9=3:N, N with 27 digits.

29N+9=3 0…0, 27 zeros.

29N=2 9…9 1, 26 nines.

Therefore N=103448275862068965517241379

The smallest integer that ends with a 3 and that when that 3 is moved from the end to the beginning, makes the number 3 times as large is N:3 = 1034482758620689655172413793.

Yeah.

May 30th, 2010 at 8:23 am

I remembered there is a big calculator on my computer…

May 30th, 2010 at 9:18 am

Yeah indeed. Very well done. Your final answer was very slick.

The Windows calculator is really quite useful.

I hope that you are as amazed at the size of the number as I was when I first came across a similar problem.

May 30th, 2010 at 9:55 am

That was great Kary, thanks

May 30th, 2010 at 10:08 am

Thanks Indeed it’s a big number.

May 30th, 2010 at 3:15 pm

Since there is no limitation in the number of the digits, the smallest integer is number 3!

May 31st, 2010 at 3:11 am

mohamed. I must be blind. I’ve only just seen your answer. Excellent, the first half is practically identical to the way I solved it. Very well done.

In general you must be very careful when dividing in modulo arithmetic – the operation isn’t even defined unless you are working with a prime modulo system. Fortunately 29 is a prime.

For safety, starting at: 9 = 3*10^n (mod 29)

Multilpying both sides by 10 => 90 = 30*10^n (mod 29)

=> 3 = 10^n (mod 29)

Multilpying both sides by 10 => 30 = 10^(n+1) (mod 29)

=> 1 = 10^(n+1) (mod 29), which is what you also got.

I hope I didn’t spoil the problem by giving too many clues.

May 31st, 2010 at 4:02 am

Well, I didn’t get there before the answer was posted. Good question.

May 31st, 2010 at 6:56 am

THe related problem was on the old ToM site under the name “Little Two”. It was the same problem, but used 2 instead of 3 throughout. I think it was the first problem I solved on ToM. It also instantly hooked me to ToM.

May 31st, 2010 at 9:32 am

I dunno why it took so long for my comment to appear… It kept pending for a long while. There’re two pending threads too i guess.

BTW, where have the old ToM gone? I’ve just noticed the change some days ago .

Guys.. read Chris’s comment (#20) about modular division in modular arithmetic. It’s a serious, and excellent, note. I thought it’s quite known, but I found some mates who have no idea about that . You may also check these links:

-http://abstractnonsense.wordpress.com/2007/02/01/modular-arithmetic/

-http://www.math.harvard.edu/~sarah/magic/topics/division

Cheers.

June 1st, 2010 at 4:46 am

Most of what I know about modular/modulo arithmetic came from: http://www.cut-the-knot.org/blue/Modulo.shtml

June 1st, 2010 at 7:28 pm

Hi Konstantina. Your post also seems to have taken ages to come through. 3 doesn’t work. If you move the 3 from the end to the beginning you still have 3, but you need 9!!!

June 2nd, 2010 at 9:30 am

My apologies to Ragknot. I misread what he’d done and thought he was ONLY providing more and more accurate versions of the number sought.

October 6th, 2010 at 9:46 am

33 = 3*33 = 99

or

3 = 3*3 = 9

October 6th, 2010 at 11:42 am

Hi Jesse. Sorry, neither 3 or 33 do it. e.g. 33, move the RHS 3 to the LHS and you still have 33, so you haven’t tripled the original number. The same goes for 3.