## 29 times

Posted by Chris on January 3, 2011 – 2:51 pm

I found this on the old ToM site:

Let N be a positive integer. Find the smallest value of N (and the associated value of Y) such that 29*N = YNY (positional notation), where 1 ≤ Y ≤ 9.

e.g. I want something like: 345 * 29 = 23452

That example doesn’t work as the equation is false.

No computer programs thank you.

January 3rd, 2011 at 4:07 pm

52631579 is the answer i came up with. I’m not sure yet if it is the smallest, but it is the smallest i found with Y being 1. Here is what i did:

for a 4-digit number, 35*29=1015 is the smallest combination, 99*29=2871 is the largest. the numbers that come closest are 52*29=1508 and 52*29=1537, but neither match perfectly.

move to a 5-digit number…we see that 526*29=15254 and 527*29=15283, again just a litle off.

now let’s try a 6-digit number…5263*29=152627 and 5264*29=152656, so close.

now at this point i noticed a pattern of 52->526->5263…

expanding by one number each time i get:

52 * 29 = 1508

526 * 29 = 15254

5263 * 29 = 152627

52632 * 29 = 1526328 <-if only the 8 were a 1…

526316 * 29 = 1563164 <-dang…the 4 isn't a 1 either

5263158 * 29 = 152631582 <-2 is getting closer to 1..

52631579 * 29 = 1526315791

yay! it worked.

the only thing i didn't check is any sequence that finds a smaller N that reaches the YNY quicker if Y were anything other than 1. I'll let someone else try for Y=2,3,4…

January 3rd, 2011 at 4:28 pm

Dusty, dusty math…

29N = YNY, where N is not a fixed number of digits could be mathematically represented as:

29N = Y + 10N + Y*10^[1 + roundup(log10(1+N))]

I have no idea how to solve for N.

Does using this formula limit us to only one N per Y?

Y = 19N / (1 + 10^[1 + roundup(log10(1+N))])

January 3rd, 2011 at 4:32 pm

good problem Chris.

shortly after i posted my first response, i realized that I should be fully confident in my first answer.

let’s take a 5 digit number with Y=2…

20002/29~688 and 999*29=28971. there is no number between 688 and 999 that will make for a 2xxx2 number just by looking at the 28971. for the same reason, there will never be a Y>1 number, and so my 52631579 is my final answer.

by the way, the next number in the sequence is….well i don’t know. I tried to find out for fun, but my calculator won’t go that far, and neither will microsoft excel. I do know that N is atleast 14 digits following my previous pattern. 5263157894737…

January 3rd, 2011 at 4:47 pm

Hi DP. As you have realised, you have got the correct answer.

Hi cazayoux, that’s a good start.

I haven’t solved it myself. If you let N be n digits long (rather than that log expression) and use modulo arithmetic, I’m pretty sure you’ll get there (more elegantly, I expect).

If you want, take a look at http://trickofmind.com/?p=72 for a guide.

It’s a good problem too, so you may want to tackle it before peeking at the method.

I’m not sure if you’d then be able to rattle off all such numbers after that.

January 4th, 2011 at 10:01 am

29N = YNY, 1<=Y<=9, N is an variable number of digits

If N = 1 digit,

29N = 101Y + 10N

19N = 101Y

N = (101/19)Y

N for 2 digits = (1001/19)Y

N for 3 digits = (10001/19)Y

:

:

So I'm looking for N to be a whole number when Y = [1..9]

The only way N can be whole is if Y is divisible by 19, or the numerator (101, 1001, ….)

Y can't be divisible by 19 (bounded by 1 and 9)

So we test 101/19, then 1001/19, then 10001/19, and so on until we find a whole number.

1000000001 / 19 = 52631579 !!!

So N = 52631579Y

So what values of N for Y = 1..9

that

satifies 29N = YNY

If Y = 1, then 29N = 1N1 … 29*52631579 = 1526315791 !!!

Bingo.

I checked for other values of 9 for this value of N and did not find a solution.

Now I'm curious about the lowest satisfactory N for each Y (2,3,…) or even for Y as a multiple of 19.

January 4th, 2011 at 10:43 am

Hi cazayoux, that’s pretty good. I have just finished writing up a solution. Because of the that, I now know that Y can only be 1. I have explicitly calculated the first 3 and have an expression for all of them.

I’ll wait a little longer before publishing.

January 4th, 2011 at 8:37 pm

It’s just gone 3:35 am here (England). I’ll post my solution in about 10 hours from now.

January 5th, 2011 at 2:23 am

Let me save Chris some work and try to fool my hangover: Let N be a k-1 digit number. Then 29N=YNY is equivalent to 19N=y(10^k+1). Since (y,19)=1 (i.e., they are co-prime) we need 10^k+1 to be divisible by 19. 19 is a prime number, so by Fermat Theorem we know that 10^18=1 (mod 19). Hence, either 10^9=1 mod 19 and then the problem has no solutions, or 10^9=-1 mod 19 and N is at least an 8-digit-number. Direct computation verifies the second case and we conclude that k should be of the type k=19k1+9, where k1 is a non-negative integer. Now N=y(10^k+1)/19 needs to be a k-1 digit number. Assuming y>=2 we have N>2(10^k+1)/19>2(10^k+1)/20>10^(k-1) and, thus, N has at least k digits. Contradiction. Hence, y=1 and all the solutions to the problem are of the type N=(10^k+1)/19, with k=19k1+9.

January 5th, 2011 at 7:40 am

Let N represent the number of interest, then we have:

29*N = Y:N:Y where “:” => string catenation.

Let N be n digits long, then

29*N = Y*10^(n+1) + 10*N + Y, rearranging =>

19*N = Y*(10^(n+1) + 1)

So Y*(10^(n+1) + 1) = 0 (mod 19)

But Y is 1,2,3,4,5,6,7,8 or 9 and none of those = 0 (mod 19)

So 10^(n+1) + 1 = 0 (mod 19)

=> 10^(n+1) = 18 (mod 19)

NB Y can’t be 0 either, as that would imply that 10 = 29.

Sadly, I now resort to trial and error. Letting n = 1,2,3,… we get (all mod 19)

10^(n+1) = 5,12,6,3,11,15,17,18,… we first get the match when n = 8

So 19*N = Y*(10^9 + 1) => N = Y*(10^9 + 1)/19 = Y*52631579

If Y > 1, then N would be > 8 digits. So Y = 1 is the only possibility.

We can add 18 to n because Fermat’s Little Theorem:

a^(p-1) = 1 (mod p) holds. NB a must be co-prime to p, as it is in our case.

i.e. 10^18 = 1 (mod 19). Because 10 and 19 are co-prime, it is guaranteed

that no smaller increment, to n, than 18 will do the trick.

So, the next time the equation is satisfied is when n = 18+8 = 26,

then N = Y*52631578947368421052631579 and we must have Y = 1.

Next n = 18+26 = 44 =>

N =52631578947368421052631578947368421052631579

I notice that the number always appears to be of the form 5263…1579,

in fact more than that is clear, on inspection. But, offhand, I don’t know

how to prove that that is always true (for the trailing digits). But each

time, the (10^(n+1) + 1)/19 part increases by a factor very close indeed

to 10^18, and that becomes more exact as we try larger n. So the first

few digits must always be the same, and so Y must be 1 for all solutions.

Hence the general solution is: N = (10^(9+18k) + 1)/19, for k = 0,1,2,3…

NB There was nothing in those calculations that required that N began with a non-zero digit, so there is no solution like N = 01234.

NB Fermat’s Little Theorem is well worth reading up on.

e.g. if a was not co-prime to p, then it would have a factor p and then

we could write a = mp, then a^n = (mp)^n = m^n * p^n = 0 (mod p).

But if a is co-prime to p then a^n (mod p) cannot be 0. Also, as we

increment n, we must find a^n = 1,2,3,…,p-1 (mod p), although not

necessarily (if ever!!!) in that order.

January 5th, 2011 at 8:20 am

Hi Slavy. I’d aready written up my solution, so I only had to do a copy/paste.

I like the solutions 10^9 = ±1 (mod 19) from 10^18 = 1 (mod 19). That’s a really nice labour saver. Thank you for publishing it.

January 5th, 2011 at 8:35 am

not that i completely kept up with all of that, but i did notice a longer pattern that what you noted…

526315789473684210 repeats (18 digits), then the first 8 digits (last one rounded).

Thanks for keeping my brain active. i need things like this with my copy-paste type job.

January 5th, 2011 at 8:58 am

Hi DP. Yep, I vaguely referred to the longer patterns in my 4th from last para. But the important bit was the first few digits, as I was trying to establish that Y = 1 always.

But I came back to this page, having just had a bath, and with Slavy’s neat trick burning into my brain.

If I’d thought of that before, I would have done some of it a bit differently. Starting at 10^(n+1) + 1 = 0 (mod 19)

=> 10^(n+1) = -1 (mod 19), NB -1 rather than 18.

Then squaring => 10^(2(n+1)) = 1 (mod 19).

But by FLT, 10^18 = 1 (mod 19) and so 2(n+1) = 18 => n = 8. No trial and error needed, yahoo. It takes up more lines, but is so much more elegant and it saved lots of boring calculations.

However, I squared and Slavy square-rooted (I hadn’t ever thought to do that). I’m going to have to give that (and extensions to e.g. cube-rooting) some thought.

I wonder how many other times that would have saved me some effort.

January 11th, 2011 at 1:25 pm

I stumbled across more about that square-rooting stuff. It seems that starting with FLT a^(p-1) = 1 (mod p) then it is the case that

a^((p-1)//2) = ± 1 (mod p) is generally true. the LHS is so common that a shorthand way of writing was created, it is called the Legendre symbol, and is used heavily in topics like quadratic reciprocity.