Java Program to Find Smallest Integer with Same Last 5 Digits as its 7th Power

In summary, the conversation discusses a program built to find the smallest integer greater than 2006 that has the same last five digits when raised to the 7th power. The solution is found to be 75800, but when checked on a calculator, the last five digits do not match. The conversation then turns to using the java.math.BigInteger class to handle large numbers and provides a code example. The use of strings in calculations is discouraged and a more efficient method is suggested. The conversation also explores a similar solution in Haskell using list comprehension and explains how Haskell's lazy evaluation works. Finally, the conversation discusses finding the 11th element of an infinite list and the use of set comprehension in Haskell.
  • #1
muna580
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: 
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;

    }
}
 
Technology news on Phys.org
  • #2
How big is 75800^7?
 
  • #3
On my calc is a huge number, more than 35 digits
 
  • #4
How big of a number can your code handle correctly?
 
  • #5
First I would like to point out the result of typing the following line into Haskell's ghci:
Code: 
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:
  • #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?
 
  • #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: 
BigInteger bigFive = new BigInteger("5");

or

BigInteger bigFive = BigInteger.valueOf(5L);

Multiplying

Code: 
BigInteger bigFiveTimesFive = bigFive.multiply(bigFive);

Modulo

Code: 
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: 
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: 
	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, shouldn't the result be a set of all numbers greater than 2006 which satisfy the conditions?

Result should be set of 9375,9376,18751,31249...
 
  • #8
haki said:
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, shouldn't the result be a set of all numbers greater than 2006 which satisfy the conditions?

Result should be set of 9375,9376,18751,31249...
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:
  • #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?
 
  • #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?
 
  • #11
haki said:
Very cool. I tryied it myself with Haskell but I got the 11th element to be 90624.
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.
Anyway, how do you tell Haskell that x is a Real number does Haskell know about Natural numbers, Real numbers and such?
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.

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.
Yeah, let me know if you find a way around that besides closing the prompt.

I found a large list of tutorials/manuals on the Haskell site, do you have any recommendations on which to use?
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.
 
  • #12
muna580 said:
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?

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.
 
  • #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.
 
  • #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.
 
  • #15
muna580 said:
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.

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:
  • #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?
 
  • #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?
 
  • #18
haki said:
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?

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

FAQ: Java Program to Find Smallest Integer with Same Last 5 Digits as its 7th Power

How does the Java program find the smallest integer with the same last 5 digits as its 7th power?

The Java program uses a loop to iterate through all possible integers until it finds one that meets the criteria. It then uses the modulus operator to check if the last 5 digits of the integer match the last 5 digits of its 7th power. If a match is found, the program returns that integer as the smallest one with the same last 5 digits as its 7th power.

What is the purpose of finding the smallest integer with the same last 5 digits as its 7th power?

The purpose of this program is to demonstrate the concept of modular arithmetic, where the remainder of a number is used to determine certain patterns or properties. In this case, we are looking for a specific pattern in the last 5 digits of a number and its 7th power.

Is there a limit to the size of the integer that can be used in this program?

Yes, there is a limit to the size of the integer that can be used in this program. Java has a maximum value for integers, which is 2,147,483,647. If the smallest integer with the same last 5 digits as its 7th power is larger than this value, the program will not be able to find it.

Can this program be modified to find the smallest integer with the same last 3 digits as its 4th power?

Yes, this program can be modified to find the smallest integer with the same last 3 digits as its 4th power. The code can be adjusted to use a different number of digits and power. However, the larger the number of digits and power, the longer it may take for the program to find a match.

How can I test if the program is working correctly?

You can test the program by inputting different integers and checking if the output is the smallest one with the same last 5 digits as its 7th power. You can also use a mathematical calculator to verify the result. Additionally, you can modify the code to print out all the integers and their respective 7th power with the same last 5 digits, and manually check if the output is correct.

Similar threads

MHB Approximating the Double Integral using Monte Carlo Method
Replies
1
Views
1K
Java [Java] Did I write this program correctly? Please check
Replies
5
Views
2K
Engineering HL Programming: Mini-Assembler in Java
Replies
7
Views
2K
Java Why Are FFT Frequencies Inaccurate in My Java Program?
Replies
5
Views
5K
Java Why Does My Java Graph Show Incorrect E Field Values?
Replies
4
Views
2K
Java Checking for Prime Digits in a Number
Replies
2
Views
40K
Java Question about this java program
Replies
6
Views
4K
Java Why Does This Java Code Only Store One Answer in an Array?
Replies
2
Views
2K
Comp Sci Using methods in java programming
Replies
1
Views
2K
Java Create Dynamic Ladder with Java | Learn to Code Java Graphics
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top