Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple Java Program Help

  1. Oct 26, 2006 #1
    I have built a program to answer the follwoing question.

    What is the smallest integer x >2006, such that x^7 and x terminate in the same five digits.

    The answer I get is 75800. But when I punch in 75800 in the calculator, for some reason, the last 5 digits for this number and 75800^7 are not equal. Why?

    Code (Text):
    import java.lang.Math;
     
    public class Number21
    {
        public static void main (String[] args)
        {
            int result = Solve21(2006);
            System.out.println("Number21 is: " + result);
            System.out.println("Number21 rised to 7th power is: " + Math.pow(result,7));
        }
       
        public static int Solve21(int x)
        {

            int ANSWER =0;
            boolean found = false;
            int n = x;
           
            while (!found)
            {
           
            long npow = (long)Math.pow(n,7);
            String nStr = String.valueOf(n);
            String npowStr = String.valueOf(npow);
           
            if (n <= 9999)
            {
                nStr = "0"+nStr;
            }
           
            int nStrLength = nStr.length();
            int npowStrLength = npowStr.length();
           
            String nStrSub = nStr.substring((nStrLength-5),(nStrLength-1));
            String npowStrSub = npowStr.substring((npowStrLength-5),(npowStrLength-1));
           
            if (nStrSub.equals(npowStrSub))
            {
                ANSWER = n;
                found = true;
            }
           
            //System.out.println("Currently N is: " + n);
           
            n++;
               
            }
           
            return ANSWER;

        }
    }

     
     
  2. jcsd
  3. Oct 26, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How big is 75800^7?
     
  4. Oct 26, 2006 #3
    On my calc is a huge number, more than 35 digits
     
  5. Oct 26, 2006 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How big of a number can your code handle correctly?
     
  6. Oct 26, 2006 #5

    0rthodontist

    User Avatar
    Science Advisor

    First I would like to point out the result of typing the following line into Haskell's ghci:
    Code (Text):

    Prelude> head [x | x <- [1..], mod x (10^5) == mod (x^7) (10^5), x > 2006]
    9375
    Total coding time: under 1 minute. This could have been made a tiny bit more efficient by just saying x <- [2007..] and dispensing with x > 2006.


    As Hurkyl implied, you should use the java.math.BigInteger class because a variable of type long can't store 9375^7 = 72419643402099609375. Another problem I see is that java's substring method on input a, b returns the substring starting at position a, and ending just before position b. So the second argument to your substring methods should be nStrLength and npowStrLength, not nStrLength-1 and npowStrLength-1. (also, there is no reason to define those string lengths as separate variables, you can just call the length() function when you need it).
     
    Last edited: Oct 26, 2006
  7. Oct 26, 2006 #6
    Well, I am so confused about how to use the BigInteger class. How do I raise that number to the 7th power using big integer? Then after, how do I get the value in the STRING format?
     
  8. Oct 27, 2006 #7
    Be careful when you use your calculator, if they cannot display large numbers they do some rounding or worse give you an error.

    Anyway, using BigInteger is relatively straight forward.

    Creating a new BigInteger

    Code (Text):

    BigInteger bigFive = new BigInteger("5");

    or

    BigInteger bigFive = BigInteger.valueOf(5L);
     
    Multiplying

    Code (Text):


    BigInteger bigFiveTimesFive = bigFive.multiply(bigFive);

     
    Modulo

    Code (Text):


    BigInteger remainder = bigFive.mod(new BigInteger("3"));
     
    for more info see here

    http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html

    You shound't be using Strings in this case try to avoid them in numerics. Just do mod 1e5 and compare the result e.g.

    Code (Text):

    BigInteger.valueOf(123L).mod(new BigInteger("100")).equals(new BigInteger("23"));
     
    Ugly I know, but is relatively straight forward.

    here is the whole code - time taken 5 mins

    Code (Text):


        public static void main(String[] args) {

       
            // if we mod with this the result are the last 5 digits
            // e.g. 13213456 mod 1e5 is 13456, the last five digits.
            BigInteger modDivider = BigInteger.valueOf((long) 1e5);

            // will test long's from 2007 to the max number an long can hold
            for (long i = 2007; i < Long.MAX_VALUE; i++) {

                // create a new BigInteger with the value of x
                BigInteger x = BigInteger.valueOf(i);

                // take the x to the 7th power
                BigInteger xToThe7ThPower = x.pow(7);

                // check if the last five digits are the same using the mod trick

                if (x.mod(modDivider).equals(xToThe7ThPower.mod(modDivider))) {
                    // print the result
                    System.out.println("HEUREKA!!! ");
                    System.out.println("x " + x);
                    System.out.println("x^7 " + xToThe7ThPower);
                    // exit the method - no use of looping
                    return;
                }

            }
        }

     
    Whow Haskell code is cool, set notation? I want a set where x has the values from 1 to inf, where x mod 1e5 is the same as x^7 mod 1e5 and x is greater than 2006, very cool. I just don't understand how does Haskell know you are doing with the set of Z - Integers and how does it know to stop when it finds the first one, shouldnt the result be a set of all numbers greater than 2006 which satisfy the conditions?

    Result should be set of 9375,9376,18751,31249....
     
  9. Oct 27, 2006 #8

    0rthodontist

    User Avatar
    Science Advisor

    The set notation thing--called a list comprehension--IS that infinite list--I just took the head of it (the first element of it). Haskell has something called lazy evaluation which means that it doesn't calculate any values until it actually needs them for another computation. You can say [x | x <- [1..], mod x (10^5) == mod (x^7) (10^5), x > 2006] which literally means an infinite list of numbers, and you can ask for, say, the 11th element of that list by saying [x | x <- [1..], mod x (10^5) == mod (x^7) (10^5), x > 2006] !! 10 which equals 99999, but until you asked for the 11th element Haskell didn't bother to compute it. Logically, the list contains an infinite amount of numbers and you can treat just as if it really did, but computationally Haskell will only compute the ones you need.
     
    Last edited: Oct 27, 2006
  10. Oct 27, 2006 #9
    Very cool. I tryied it myself with Haskell but I got the 11th element to be 90624. Anyway, how do you tell Haskell that x is a Real number does Haskell know about Natural numbers, Real numbers and such? I tried for example to give the solution of a quadratic equation as set comprehension,

    [x | x <- [2000...] , x^2 == 4] , never finishes, very smart, very bad since I didn't found a key config to stop it. I tried the standard control + C but that didn't accomplish anything.

    I found a large list of tutorials/manuals on the Haskell site, do you have any recommendations on which to use?
     
  11. Oct 27, 2006 #10
    Wow, haki, thanks alot. Your great.

    But I have one question. Thanks for making the program for me. I got the answer, using the program. BUt i have a question about the program that you made.

    I don't really understand this whole "mod" thingy. What is mod? According to Sun Java, they define mod by saying: Returns a BigInteger whose value is (this mod m). This method differs from remainder in that it always returns a non-negative BigInteger.. But I don't really understand what it means.

    BigInteger modDivider = BigInteger.valueOf((long) 1e5);
    if (x.mod(modDivider).equals(xToThe7ThPower.mod(modDivider)))

    I am so confused right now that its not even funny. lol But please, can you explain me this whole mod concept?

    Alson, I had one more question.

    What is the diffrence between long and int? What is the diffrence between float and double?
     
  12. Oct 28, 2006 #11

    0rthodontist

    User Avatar
    Science Advisor

    Oh, you're right. I have no idea how I made that mistake--99999 is the 13th element so it's not even an off-by-one.
    Well, you might say (5::Double) or (5::Fractional a=>a) to indicate specifically that you want 5 to be part of a set of numbers that includes 5.4. Haskell will usually infer the type for you if you don't say it explicitly. In this case it will infer that the infinite list is of type (Integral a => [a]) which means it is a list containing variables of type a, where a is of the class Integral, which is the class containing Ints and Integers (and any other user-defined whole numbers). You could force the list to be of type [Int] (a list of Ints) by saying head ([x | x <- [1..], mod x (10^5) == mod (x^7) (10^5), x > 2006] :: [Int]) which would give you the unusual (wrong) result 10399 because of overflows. You can check the type of an expression in ghci with the :t command.

    Yeah, let me know if you find a way around that besides closing the prompt.

    I don't know--I read Haskell for C Programmers and some other ones. It is useful to have a Prelude reference such as http://www.haskell.org/onlinereport/standard-prelude.html at hand.
     
  13. Oct 28, 2006 #12
    Confusion is generally a good thing means that you are thinking. Home work from a programming lesson?

    Well mod - modulo it is the remainder afer Integer division, that is for example

    13 / 6 = 2 * 6 + 1 = 12 + 1 = 13, the modulo is 1, soo 13 mod 6 = 1

    0 / 6 = 0 *6 + 0, the modulo is 0, soo 0 mod 6 = 0

    20 / 3 = 6 * 3 + 2, the modulo is 2, soo 20 mod 3 = 2

    you get the general idea?

    123 mod 100 is .... 23 since 123 / 100 = 1 * 100 + 23

    if (x.mod(modDivider).equals(xToThe7ThPower.mod(modDivider)))

    you can picture this as

    x % 100 == x^7 % 100

    where % is the modulo operator. But since BigInteger is an object you must call methods on it and use the equals sign to comapare object and not == operator.

    For int/long and float/double put in your favorite search engine "Java primitive types". The reasons there is (long)1e5 is because 1e5 is for Java an double number but the method expects an long number soo we did a cast - that is said ok you can use double for long value and we agree that you can get rid of the decimal part. Since 1e5 is for Java 100000,000000000XXXXXXXXXXX where X is some number other than 0 due to the fact you cannot store more than 15 digits in a double precisely casting it to long will convert it to 100000. Alternatively you could have written BigInteger.valueOf(100000L);

    It might be a bit confusing at first but after some time it really shouldn't.
     
  14. Oct 28, 2006 #13
    Argh, just checked the library there is only one suitable book on Haskell called "Haskell : the craft of functional programming" and it is has no specified return date, probably on some book shelf of some assistant or prof. Oh well tutorials will have to do.
     
  15. Oct 28, 2006 #14
    Haki, thanks for your explantion, but I am still confused a little.

    1. What is the diffrence between x.remainder(y) and x.mod(y). According to your explanion of mod, your telling me we are just getting the remainder.

    2. Also, in my case, we are getting the last 5 digits of number. Why would we even use the mod or the remiander method to get the last 5 digits?

    3. What is 1e5?

    4. x % 100 == x^7 % 100. Why 100? Sorry even though I am smart at math, when it somes to simple and basic math, I forget all the primitve math.
     
  16. Oct 29, 2006 #15
    1. Doh, they are the same with a subtle difference mod always returns a positive number while the remainder returns a negative number for a negative value!

    Yes! In java - 13 % 6 = -1 That is for a negative number you got a negative remainder!

    2. How else do you supose we compare the last 5 digits?

    3. 1e5, you have a calculator? It has a button labeled ee well this is the same 1e5 = 1 * 10^5, scientific notation. Since it is easier and clearer than 100000, how many zeros again? e5 -> ah 5 zeros.

    4. Well if you are doing with primities

    int a = 10;
    int b = 3;

    System.out.println(a + b); // prints 13;
    System.out.println(a % 3); // prints 1;

    BigInteger bigA = BigInteger.valueOf(10);
    BigInteger bigB = BigInteger.valueOf(3);

    bigA.mod(bigB); is equivalent to

    10 % 3 but it is not the same.

    BigIntegers stuff is arbitrary precision while int is of about 7 digits precision, and mod will always return a positive number where % returns negative value if the number is negative.
     
    Last edited: Oct 29, 2006
  17. Oct 29, 2006 #16
    Oh okay, I understand now, but I still don't understand the concept of how you are retreving the last 5 digits of each number. Yea, I know mod, remiander...... But what is the formula to get the last 5 digits and why or where did you learn it?
     
  18. Oct 29, 2006 #17
    WHAT IS THE FORMULA???? What kind of joke is that.

    Btw: how do you convert from base 10 number to base 2 number? The mod thingy, why not use it for something else?
     
  19. Oct 29, 2006 #18
    What does it mean to convert bases? Sorry, but i never understood the whole system of bases and stuff. Also, please can you explain to me how did you get the last 5 digits?
     
  20. Oct 29, 2006 #19
    The last five digits part is explained read a few posts back, if you mod with 10 you get last digit if you mod 100 you get last two digits etc.

    You should have covered the bases and stuff at school.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?