Subscribe via feed.

## 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.

This post is under “MathsChallenge” and has 13 respond so far.

### 13 Responds so far- Add one»

1. 1. DP Said：

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…

2. 2. cazayoux Said：

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))])

3. 3. DP Said：

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…

4. 4. Chris Said：

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.

5. 5. cazayoux Said：

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.

6. 6. Chris Said：

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.

7. 7. Chris Said：

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

8. 8. slavy Said：

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.

9. 9. Chris Said：

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.

10. 10. Chris Said：

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.

11. 11. DP Said：

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.

12. 12. Chris Said：

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.

13. 13. Chris Said：

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.

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0