Subscribe via feed.

Lowest Value of n is 404?

Posted by Karl Sharman on August 14, 2014 – 5:07 am

Where the numbers 2n and 5n (where n is a positive integer) start with the same digit, what is the lowest possible value of n? The numbers are written in decimal notation, with no leading zeroes. I am going to get flak for this…. but, I have broad shoulders!

Tags:
This post is under “Tom” and has 11 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

11 Responds so far- Add one»

  1. 1. Chris Said:

    Hi Karl, do you mean 2*n and 5*n or do you mean the two numbers actually atart with 2 and 5? Also, is it that n doesn’t start with 0?

  2. 2. Karl Sharman Said:

    Hi Chris – 2*n and 5*n
    Neither n, nor the products start with leading zeroes.

  3. 3. jan jansen Said:

    impossible is what i say

  4. 4. Chris Said:

    I agree with Jan. I’m pretty sure that I know how to prove it by contradiction. The starting point for my wannabe proof is: if N is the smallest value of n that satisfies the problem, then 10N, 100N, 1000N, … also satisfy the common leading digit requirement.

    Later. That doesn’t look so promising now.

  5. 5. Karl Sharman Said:

    Error 404 – File not found…

    The key insight is to note that 2n × 5n = 10n. From here, it is clear that if 2n and 5n begin with the same digit, that digit must be either 1 (if 2n and 5n are both powers of 10), or 3. Since n > 0, we reject the former case; hence the first digit must be 3. (If the first digit of 2n is less than 3, then the first digit of 5n must be greater than or equal to 3. If the first digit of 2n is greater than 3, then the first digit of 5n must be less than 3.)
    More formally, if 2n and 5n begin with the digit d, then
    • d x 10r < 2n < (d + 1) x 10r, and
    • d x 10s < 5n < (d + 1) x 10s, for some non-negative integers r and s.
    (We have strict inequality because, for n > 0, 2n 0 (modulo 10) 2n 0 (modulo 5), which is impossible by the Fundamental Theorem of Arithmetic. Similarly for 5n 0 (modulo 10).)
    Multiplying the inequalities, we obtain d2 x 10r+s < 10n < (d + 1)2 x 10r+s.
    Hence 1 is less than or equal to d2 < 10n−r−s < (d + 1)2 100. (Since d is a decimal digit.)
    It follows that n − r − s = 1, so that d2 < 10 < (d + 1)2, and d = 3.
    Therefore, if the numbers 2n and 5n (where n is a positive integer) start with the same digit, then that digit must be 3.

    Whilst we did not prove above that there are any values of n for which 2n and 5n both begin with the same digit; we proved only that if such examples exist, then that digit must be 3. However, it is easily seen that such examples do exist. The first few cases are: n = 5, 15, 78, 88, 98, 108, 118, 181, 191, 201, 211, 274, 284, 294, 304, … . Notice that there tend to be runs of several numbers with a difference of 10. This is because 2^10 is congruent to 10^3 and 5^10 is congruent to 10^7. (ASCII for wavy equal sign?)

  6. 6. Wizard of Oz Said:

    Hi Karl,

    You lost me in at least a couple of places in Post # 5.

    Starting with your list of “solutions” at the end: n = 5, 15, 78, etc. If n = 5 then 2n = 10 and 5n = 25. Neither of these start with the same digit or with 3. Same with most of the others.

    Then at the beginning you state that 2n x 5n = 10n. This should obviously be 10n^2. It’s not clear to me that this then leads to the first digit of 2n and 5n both being 3.

    What am I missing?

  7. 7. Zorglub Said:

    I was also confused by this problem. But it makes perfect sense if one reads 2^n and 5^n instead of 2n and 5n. Big difference.

  8. 8. Chris Said:

    I’m lost too. I’m not sure when 2n means 2*n or 2^n etc.

  9. 9. Chris Said:

    Thanks Zorglub, you’re right, the solution makes sense if the question is for 2^n and 5^n, rather that 2*n and 5*n, having the same leading digit. If that is the case, then it would have been easier (but less interesting) to use trial and error to find n = 5 => 2^5 =32 and 5^5 = 3125 is the smallest n.

    Here’s my attempt at fixing Karl’s solution:

    The key insight is to note that 2^n × 5^n = 10^n. From here, it is clear that if 2^n and 5^n begin with the same digit, that digit must be either 1 (if 2^n and 5^n are both powers of 10), or 3. Since n > 0, we reject the former case; hence the first digit must be 3. (If the first digit of 2^n is less than 3, then the first digit of 5^n must be greater than or equal to 3. If the first digit of 2^n is greater than 3, then the first digit of 5^n must be less than 3).
    More formally, if 2^n and 5^n begin with the digit d, then
    • d x 10^r < 2^n < (d + 1) x 10^r, and
    • d x 10^s < 5^n < (d + 1) x 10^s, for some non-negative integers r and s. We have strict inequality because neither 2^n nor 5^n can be divisible by 10 (by the fundamental theorem of arithmetic).

    Multiplying those together => d^2 x 10^(r+s) < 10^n < (d + 1)^2 x 10^(r+s). Dividing throughout 10^(r+s) => 1 ≤ d^2 < 10^(n-r-s) < (d+1)^2 ≤ 100. (Since d is a decimal digit). It follows that n − r − s = 1, so that d^2 < 10 < (d + 1)^2, and d = 3. Therefore, if the numbers 2^n and 5^n (where n is a positive integer) start with the same digit, then that digit must be 3.

    Whilst we did not prove above that there are any values of n for which 2^n and 5^n both begin with the same digit; we proved only that if such examples exist, then that digit must be 3. However, it is easily seen that such examples do exist. The first few cases are: n = 5, 15, 78, 88, 98, 108, 118, 181, 191, 201, 211, 274, 284, 294, 304, … . Notice that there tend to be runs of several numbers with a difference of 10. This is because 2^10 ≈ 10^3 and 5^10 ≈ 10^7, the difference is only 2.4%.

    This still leaves as unknown whether 2*n and 5*n can have a common leading digit.

  10. 10. Zorglub Said:

    In answer to Chris’ last comment on 2*n and 5*n:

    d x 10^r ≤ 2*n ≤ (d + 1) x 10^r, and
    d x 10^s ≤ 5*n ≤ (d + 1) x 10^s with r ≤ s.

    CASE 1: r = s.

    2.5 = (5*n) / (2*n)
    ≤ ((d + 1) x 10^r) / ( d x 10^r)
    = 1 + 1/d
    ≤ 2
    Contradiction.

    CASE 2: r < s. i.e. r+1 ≤ s

    2.5 = (5*n) / (2*n)
    ≥ (d x 10^s) / ( (d + 1) x 10^r)
    ≥ (d x 10^(r+1)) / ( (d + 1) x 10^r)
    = 10*d /(d+1)
    = 10 /(1+ 1/d)
    ≥ 5
    Contradiction.

  11. 11. Chris Said:

    Thank you Zorglub. That looks pretty neat.

Post a reply




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