当前位置:首页 » Project Euler » 详细页

Square digit chains 题号:92 难度: 5 中英对照

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 11
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Solution

题目中的number chain指的是$$44->(4\times4+4\times4)=32->(3\times3+2\times2)=13->(1\times1+3\times3)=10->(1\times1+0\times0)=1$$ 所有的数按照这个numebr chain运算下去最后结果只有1和89两种情况,要求[1,10^8]区间内的数经过number chain运算后最后为89的数的个数 所以只要判断区间内的每个数最后是到达1还是89即可 取一个整数n的每一位的平方和,只要在满足n!=0的情况下$$digits=n%10$$$$n=n/10$$$$sum+=digits*digits$$即可

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class p92 {
	private static final int MAX_N=10000000;
	//private static final int MAX_N=30;
	public static void main(String[] args){
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	public static long run(){
		long count=0;
		for(int i=1;i<MAX_N;i++){
			if(is89(i)){
				count++;
			}
		}
		return count;
	}
	
	public static boolean is89(int n){
		while(true){
			switch(n){
			case 1:return false;
			case 89:return true;
			default: n=nextNumber(n);
			}
		}
	}
	
	public static int nextNumber(int n){
		int sum=0;
		while(n!=0){
			int yushu=n%10;
			n=n/10;
			sum+=yushu*yushu;
		}
		//System.out.println(sum);
		return sum;
	}
}
8581146
1214ms