CODEWITHSUNDEEP
calgorithm
yiping
yiping

Reputation: 55

How to calculate the Kaprekar numbers in a better way?

#include <stdio.h>
long power(long y);

int main(void)
{
    long long first, second, number, kaprekar;
    int exponent;
    int helper;
    printf("Let's see all n digits number Kaprekar number\n");
    scanf("%d", &exponent);
    helper = exponent / 2;
    printf("Here are Kaprekar numbers\n");
    for (number = power(exponent - 1); number <= (power(exponent) - 1); number++)
    {
        first = number / (power(helper));
        second = number - (first*(power(helper)));
        if ((first + second)*(first + second) == number)
            printf("%lld\n", number);
    }
    return 0;
}

long power(long y)
{
    long i;
    long j = 10;
    for (i = 1; i< y; i++)
       j *= 10;

    return j;
}

First, Kaprekar number is divide the even digits number (like 2010, 102030, 2111, it has even digits, but do have to be even) into two parts, for example, 3025, dividing into two parts, 30 and 25, and (30+25)^2 = 3025. I write a program in order to calculate 14 digits number, but the program runs to slow (in fact, i can get answers until 8 digits number (for example,24502500).

so, can anyone give a better algorithm? Here is my code.

Upvotes: 3

Views: 2727

Answers (1)

hacatu
hacatu

Reputation: 665

Every Kaprekar number with 2n digits is the square of a number with n digits, so to find all of the Kaprekar numbers below 10^14, inspect the squares of all numbers below 10^7. However, the square of some n digit numbers is only 2n - 1: these will not work. To avoid these, for every power of 10 <= 10^7, start at that power divided by the square root of 10 and go up to that power of ten. I wrote a program that does this, and it runs in 0.6 seconds. The reason it is so much faster is because it is checking only about 10^6.5 numbers whereas your program checks 10^14.

#include <stdio.h>
#include <inttypes.h>

const uint64_t DIGITS = 14;

int main(void){
    uint64_t top = 10;
    for(uint64_t i = DIGITS/1; i-- > 0;){//calculate 10^(DIGITS/2) using iterated multiplication (better exponentiation is unnecessary.)
        top *= 10;
    }
    for(uint64_t t = 10; t <= top; t *= 10){
        for(uint64_t n = t*.316227766016838L; n < t; ++n){//divide t by the square root of 10 to ensure n*n has twice as many digits as n.
            uint64_t k = n*n;
            if(n == k%t + k/t){
                printf("%"PRIu64"\n", k);
            }
        }
    }
}

I hope this is helpful.

Upvotes: 3

Related Questions