Results 1 to 11 of 11
Like Tree2Thanks
  • 1 Post By johng
  • 1 Post By allthehomework

Math Help - Finding the first base that makes 16 prime and 97 a square

  1. #1
    Member
    Joined
    Sep 2012
    From
    United States
    Posts
    97
    Thanks
    21

    Finding the first base that makes 16 prime and 97 a square

    Hi guys.

    I recently encountered this problem in a math competition and still have no idea how to solve it, as I suck at number theory. Can anybody explain the solution to me? I know the answer is 53.

    What is the smallest base b where 16 is prime and 97 is a square?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Finding the first base that makes 16 prime and 97 a square

    Hey ShadowKnight8702.

    I'm not exactly sure ewhat you mean. Prime numbers are prime irrespective of the base. You could write 16 in base 10 or 8 and it would still be prime.

    Do you instead mean that if you write something in some base then the number in that base if you treated it as a number in base 10 is prime given the base 10 value (and not the intrinsic value)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2012
    From
    United States
    Posts
    97
    Thanks
    21

    Re: Finding the first base that makes 16 prime and 97 a square

    Quote Originally Posted by chiro View Post
    Hey ShadowKnight8702.

    I'm not exactly sure ewhat you mean. Prime numbers are prime irrespective of the base. You could write 16 in base 10 or 8 and it would still be prime.

    Do you instead mean that if you write something in some base then the number in that base if you treated it as a number in base 10 is prime given the base 10 value (and not the intrinsic value)?
    I will clarify. If you convert 16 base b back into base 10, it will be prime. if you convert 97 base b back into base 10, it will be a perfect square.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Finding the first base that makes 16 prime and 97 a square

    In that case, for something base b you have for a two digit number x3*b^2 + x2*b + x3 = some number and if you "interpret" it as base 10 then it means x3*10^2 + x2*10 + x3 has specific properties (like being prime).

    For a perfect square this means that the above = t^2 (for some integer t) or it is prime after conversion into base 10.

    You have the number in base b as 97 for the square and you have the square values.

    Given that there are a limited number of squares to test, you should be able to get a few equations in terms of b and solve these equations.

    To start off, I'll get you to write out the two equations: one for the square and one for the prime so that you get b's in terms of other numbers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2012
    From
    United States
    Posts
    97
    Thanks
    21

    Re: Finding the first base that makes 16 prime and 97 a square

    It is easy to see that 6 + b is prime and 9b+ 7 is a square, but I have no idea what to do with these. I know there is a way to limit how many square numbers to test, but I am unsure of that as well.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Finding the first base that makes 16 prime and 97 a square

    What is the maximum number of digits you can have and how does that restrict the number of square numbers? (For example if you are limited to less than three digits, then you can only have 9 possibilities).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    609
    Thanks
    247

    Re: Finding the first base that makes 16 prime and 97 a square

    Hi,
    The attached solution is not elegant, but it's not hard.

    Finding the first base that makes 16 prime and 97 a square-mhfbasepuzzle.png
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    609
    Thanks
    247

    Re: Finding the first base that makes 16 prime and 97 a square

    Hi again,
    I got curious about such bases. So I quickly wrote a little C program to find such. The program finds 12 such bases less than 10000, the last being 9473. I was mildly surprised that so many exist. I used floating point arithmetic to test if a given integer is a perfect square. This in general is not a good idea, but for "small" integers it's okay. Here's the code, if you're interested:

    Code:
    #include <stdio.h>
    #include <math.h>
    #define MAX 10000
    
    int isPrime(int p);
    
    int main() {
        int b=11,s,numberFound=0;
        double x;
        while (b<=MAX) {
            if (b%3==0) {
                b+=2;
                continue;
            }
            if (!isPrime(b+6)) {
                b+=2;
                continue;
            }
            x=sqrt(9*b+7);
            s=(int)floor(x);
            if (s*s==9*b+7) {
                printf("base is %d, prime is %d. square is %d = %d squared\n",
                    b,b+6,9*b+7,(int)x);
                numberFound++;
            }
            b+=2;
        }
        printf("%d bases found <= %d\n",numberFound,MAX);
        return(0);
    }
    
    /* Returns 1 (true) iff p is prime.  Upon entry, p is odd.  If p is not prime and d is the smallest proper
       divisor of p, clearly d*d<=p.
    */
    int isPrime(int p) {
        int d=3;
        while (d*d<=p) {
            if (p%d==0) {
                return(0);
            }
            d+=2;
        }
        return(1);
    }
    Last edited by johng; June 5th 2013 at 11:06 AM.
    Thanks from Gusbob
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2012
    From
    United States
    Posts
    97
    Thanks
    21

    Re: Finding the first base that makes 16 prime and 97 a square

    Is there anyway of knowing that the smallest possible base will not be in the hundreds or thousands? Cause brute forcing is fine, but it could potentially take a very long time if the smallest value of b was much higher.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    609
    Thanks
    247

    Re: Finding the first base that makes 16 prime and 97 a square

    I assume you mean generalizing the problem to:
    Given positive integers k,d_0 \text{ and }d_1, find the smallest base b with b>k,b>d_1,b>d_0,b+k\text{ prime and }d_1b+d_0\text{ a perfect square}

    I don't think there is any easy way to do this. If there were, in particular, one could easily find the smallest prime larger than 2k for a given k -- oops, very hard problem.
    Last edited by johng; June 5th 2013 at 05:50 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jun 2013
    From
    Vancouver
    Posts
    3
    Thanks
    4

    Re: Finding the first base that makes 16 prime and 97 a square

    Quote Originally Posted by ShadowKnight8702 View Post
    Hi guys.

    I recently encountered this problem in a math competition and still have no idea how to solve it, as I suck at number theory. Can anybody explain the solution to me? I know the answer is 53.

    What is the smallest base b where 16 is prime and 97 is a square?
    I literally spent the last 24 hours mulling this problem over. It's not that it's hard to do with a spread sheet, or just brute forcing it with a calculator. However, I'm assuming that in a math competition calculators are not allowed and that time is of the essence. So the real challenge is how do you handle the problem in the most efficient way?

    Obviously my long explanation takes more time than is necessary, but the point is if you have this background knowledge before the competition you could get it with little actual calculation.

    So we have b+6 = prime and 9b+7= square (x^2)

    For the prime side of things, you can eliminate a bunch of possible b's.
    Most obvious rules for b:
    b is an integer.
    b is greater than 9 (because you see the digit 9 in the examples)
    b is odd (because 6 + an even number gives an even number, hence not a prime)
    b cannot be a multiple of 3 (because 6 + a multiple of 3 gives a number divisible by 3, and thus not a prime)
    b cannot be 9, 14, 19, 24 etc because numbers in this set when added to 6 give a multiple of 5.
    You can repeat this process for 7, 11 etc however beyond 5 it doesn't help very much in terms of gain/effort.

    So, possible b's thus far: 11,13,17,23,25,31,35,37,41,43,47,53,61 etc

    That's better but it's still a lot of calculation to do on the square side of things....so that's kind of a dead end.

    It's also hard to come up with a formula that will predict primes...

    However, on the square side of things, you can have a lot more luck.

    So we have 9b+7=x^2
    solve for b
    b=(x^2-7)/9

    Is there an easy way to find all the values of x which will yield integers for b?

    Yes.

    Write the equation another way:
    b = (x^2)/9 - 7/9

    therefore (x^2)/9 must have a remainder of 7 in order for b to be an integer.

    So if you remember the divisor rule of 3s (that if the digits add to a multiple of 3, the original number is a multiple of 3) then you can extend that here.

    Side note : the divisor rule is derived as: (example)

    486 = 4(100)+8(10)+6(1)
    = 4(99+1)+8(9+1)+6
    = 4*99+4+8*9+8+6
    = 4*99+8*9+4+8+6
    The first two terms are definitely divisible by 3, and all that is left is those remainders, and if their sum is divisible by 3 then everything is.

    Using that background, we can come up with a similar rule:

    let x equal n9+R where n and R are integers, n being the number of multiples of 9 and R being the remainder {1,2,3,4,5,6,7,8}

    so:
    x^2 = (n9+R)^2
    x^2 = (n9+R)(n9+R)
    x^2 = (n9)^2 + 2Rn9 + R^2

    (n9)^2 is divisible by 9
    2Rn9 is divisible by 9

    The only thing that really matters then is that last part R^2. If (R^2)/9 equals some whole number plus 7/9, you have basically solved the problem
    R = 1 -> 1/9
    R = 2 -> 4/9
    R = 3 -> 9/9 (1)
    R = 4 -> 16/9 (or 1 and 7/9) <----this one
    R = 5 -> 25/9 (or 2 and 7/9) <----this one
    R = 6 -> 36/9 (4)
    R = 7 -> 49/9 (or 5 and 4/9)
    R = 8 -> 64/9 (or 7 and 1/9)

    So an R of 4 or 5 leads to the desired remainder.

    So x can equal n9+4 and n9+5
    {13,14,22,23,31,32 etc}

    back to b = (x^2-7)/9

    plugging into prime equation: b + 6 = (x^2-7)/9 + 6 is a prime

    you can either bruteforce from above, or you can do one more step to make it easier:
    imagine x is odd:
    (odd*odd-odd)/odd+even
    (odd-odd)/odd+even
    even/odd+even
    even+even
    even (not prime)

    imagine x is even:
    (even*even-odd)/odd+even
    (even-odd)/odd+even
    odd/odd+even
    odd+even
    odd

    therefore, x must be even, leaving {14,22,32 etc} (or basically or start with 14 then +8, +10, +8, +10 etc)

    Not much left to test...x is 22, meaning b is 53.

    Again, if you have to figure all this stuff out from scratch like I did, then it's faster to bruteforce it. If you have these tricks in your bag already, it's much more feasible.

    Please point out any mistakes you find in my reasoning.
    Thanks from ShadowKnight8702
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. surface area of a dome with a square base
    Posted in the New Users Forum
    Replies: 5
    Last Post: March 2nd 2013, 07:43 AM
  2. Replies: 3
    Last Post: February 17th 2013, 06:37 PM
  3. Prime testing with base 2 test.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 10th 2011, 01:47 PM
  4. Index form with a prime number base?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: July 20th 2010, 03:17 PM
  5. Replies: 3
    Last Post: June 15th 2008, 06:08 AM

Search Tags


/mathhelpforum @mathhelpforum