7

I wonder if it is possible to detect and/or stop infinite loop with basic java knowledge.

I got a school task(which considers our programming knowledge is on basic level) where we should take an input (int) from user and then take the sum of squares of the digits of that number (i.e. 123-->1^2+2^2+3^2). Then that result should be put in a while loop and it should repeat the same thing until it reaches 1 (i.e. 123-->1^2+2^2+3^2=14-->1^2+4^2=17-->1^2+7^2 etc)

If we get number 1 we should print "number is lucky!" and if it isn't it will be stuck in an infinite loop and we should print "number is not lucky!".

Now whats bugging me is how do they expect us to print "number is not lucky" if it will be stuck in an infinite loop ?

Is it possibly the badly written and designed task/question or there actually is a basic-level-knowledge way to detect and stop an infinite loop?

Here is my code(w/o the infinite loop detection):

import java.util.Scanner; public class Vezba { public static void main(String[] args) { boolean run = true; Scanner sc = new Scanner(System.in); int number = sc.nextInt(); int digits; int sum=0; int k = 10; int j = 1; while(run){ if(number<0){ run=false; } int len = String.valueOf(number).length(); /* Takes out each digit to make the first sum (probably redundant but please ignore)*/ while(len>0){ digits = number%k/j; j*=10; k*=10; len--; sum += digits*digits; } /* Repeats the process until sum is 1*/ while(sum>1){ int len2 = String.valueOf(sum).length(); int pom = 1; int k1=10; while(len2>0){ digits = sum%k1/pom; pom*=10; k1*=10; len2--; sum += digits*digits; } } System.out.println("Number is lucky!"); run=false; } } }
Improve this question
3
  • 15
    If you happen to solve it somehow, be prepared to accept several prizes: Halting problem. Commented Mar 6, 2015 at 13:48
  • 2
    You cannot provide a generic detection for an infinite loop. Much better to produce an exhaustive solution which cannot go into an infinite loop. A workaround is to put a time limit or a loop count limit but this is not ideal. Commented Mar 6, 2015 at 13:49
  • 1
    If you hit the same number twice you know you're in a loop, although that doesn't cover heading off towards positive or negative infinity Commented Mar 6, 2015 at 13:52

5 Answers 5

Reset to default
12

In general, there is no solution to the Halting problem.

However, in your specific case I can think of a way to detect an infinite loop. In each iteration you calculate a number (the sum of the squares of the digits or the previous number). You can put all those numbers in a Set. If in some iteration you calculate a number that is already in that Set, you know that you are stuck in an infinite loop.

Since the largest sum of squares is bound (for a number with n digits, the largest sum of squares of the digits is 81*n), there is a relatively small number of distinct values you are going to get in your iterations, so if you don't reach 1 and end with a success, you'll reach a value that's already appeared before and report a failure.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This was what I thought, however what if the number heads towards positive or negative infinity (or has ever larger scillations about a fixed point). You'd have to prove it cannot do that (or put min/max bounds)
@RichardTingle The range of an int is bounded, not that it really helps of course ;)
I'd say its just a badly written task for our level of knowledge. Set thing sounds pretty cool, first time hearing for that thing, but im eager to learn so its awesome :D And yeah your solution sounds like the only one in this case Thanks :)
@Peter true, practically speaking you'll run out of memory eventually even if you use bigInt but I'm not sure I'd count that as catching the infinite loop
@RichardTingle the sum of squares of the digits is always positive, and since an int has at most 10 digits, the sum of squares is less than 810. This means the Set would contain at most 810 numbers, and the program would terminate after at most 810 iterations.
2

While you can't provide a generic infinite loop detection, you can provide a simple one for this use case. You can make the assumption that once you repeat a number, you will always loop forever, so all you need to do is detect a repeated number.

Set<Integer> previous = new HashSet<>(); // in you loop int sum, number; do { sum = 0; int len = String.valueOf(number).length(); /* Takes out each digit to make the first sum (probably redundant but please ignore)*/ while(len>0){ digits = number%k/j; j*=10; k*=10; len--; sum += digits*digits; } } while (sum > 1 && previous.add(sum)) if (sum > 1) // no lucky.

In this case, previous.add(sum) will return false is a duplicate is detected.

Improve this answer

Comments

0

The only way is to set a max iterations number or a timeout algorithm

Improve this answer

Comments

0

First question - will the chain stretch to infinity? If you have an n-digit number, then the next number will be less than 81 * n - which is the next value after 999999.. 81n < 100n < 10^n when n>2, and all n-digit numbers are less than 10^n. So chains are bounded and must either terminate or repeat.

Second question is how to detect a loop. You could store all visited values and check against them. This is probably feasible in this case, but in general it can require a large amount of memory and time to check if a duplicate is found.

A more efficient algorithm in time and space may be to store the value found at step m/2 in the chain and compare it to the one at step m. You can think of this as trailing a lengthening piece of string behind you as you explore the solution space. Eventually (if this a loop) you will encounter the end of your string.

Improve this answer

Comments

0

Maybe you can use something like this:

n = in.nextInt(); int t = n; while (n != 0) { r = n % 10; s += Math.pow(r, 2); n /= 10; } if (s == t) System.out.println(whatever is given); else System.out.println (whatever is given);
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.