9
\$\begingroup\$

From problem #119 of the Project Euler :

The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.

The number 512 fits because :

5+1+2 = 8 and 83 = 512.

The number 17576 fits because :

1+7+5+7+6 = 26 and 263 = 17576.

There's my solution but it's extremely inefficient. I need the variable c to reach 25 but I haven't seen past 16.

    public static int c = 0;
    public static void TryAll(long x, long y)
    {
        for (int i = 2; i < 10; i++)
        {
            double powered = Math.Pow(y, i);
            if (x % y == 0 && powered == x && x % 10 != 0)
            {
                c++;
                Console.WriteLine("----- {0}", c);
                Console.WriteLine(powered);
                Console.WriteLine(y);
                Console.WriteLine(i);
            }
        }
    }
    public static void Main(string[] args)
    {
        int baseNum = 0;
        for (c = c; c < 26; baseNum++)
        {

            if (baseNum > 9)
            {
                int sum = 0;
                int baseNumD = baseNum;
                while (baseNumD != 0)
                {
                    sum += baseNumD % 10;
                    baseNumD /= 10;
                }
                TryAll(baseNum, sum);
            }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Welcome on Code Review. I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. \$\endgroup\$ – Calak Dec 9 '18 at 20:16
  • 1
    \$\begingroup\$ @Calak This code does appear to be working. It's just so slow that getting the correct answer would take an infeasible amount of time to compute. This does appear to be ontopic. \$\endgroup\$ – Carcigenicate Dec 9 '18 at 21:32
  • \$\begingroup\$ OP, can you clarify if this code is in fact producing correct answers for smaller inputs? \$\endgroup\$ – Carcigenicate Dec 9 '18 at 21:33
  • \$\begingroup\$ @Carcigenicate : "I need the variable c to reach 25 but I haven't seen past 16" that's sounds clear for me. \$\endgroup\$ – Calak Dec 9 '18 at 22:36
  • 1
    \$\begingroup\$ @Calek Code that is only broken because of TLE "errors" is considered ontopic by a mod. If that is in fact the problem (which even 200_success seems to agree is the case here), then this would be ontopic. \$\endgroup\$ – Carcigenicate Dec 9 '18 at 22:46
1
\$\begingroup\$

If you don't need to print out results in order, you can inverse the logic and compute power value first, and check if the result equals to sum of digits. It's super fast:

using System;

public class Program
{
    private const int MaxCount = 25;

    public static void Main(string[] args)
    {
        var c = 1;
        for (var i = 2; i < 100; i++)
        {
            for (var j = 2; j < 1000; j++)
            {
                var pow = (long)Math.Pow(j, i);
                var sum = SumOfDigits(pow);
                if (sum != j)
                {
                    continue;
                }
                Console.WriteLine($"{c}: {pow} = {sum} ^ {i}");
                c++;
                if (c > MaxCount)
                {
                    break;
                }
            }
            if (c > MaxCount)
            {
                break;
            }
        }
        Console.ReadLine();
    }

    private static long SumOfDigits(long value)
    {
        long sum = 0;
        while (value != 0)
        {
            sum = sum + (value % 10); 
            value = value / 10; 
        }

        return sum;
    }
}

Please note loop limit values are arbitrary, large enough to satisfy requirement of 25 results.

\$\endgroup\$
1
\$\begingroup\$
for (c = c; c < 26; baseNum++)

This line lead to "warning CS1717: Assignment made to same variable; did you mean to assign something else?"

if (baseNum > 9)

Instead of pay for a comparison in each iteration of the loop, directly set baseNum to 9.

int sum = 0;
int baseNumD = baseNum;
while (baseNumD != 0)
{
    sum += baseNumD % 10;
    baseNumD /= 10;
}

You could move this into a function, because "summing digits of number" can be reused in many other challenges.

public static void TryAll(long x, long y)

Try to use meaningful names. What does x or y mean here?

for (int i = 2; i < 10; i++)

Same here, a better name for i could be exp or exponent. Note also that 10 might be to low to handle some cases (eg: a32 = 81 920 000 000 000 000 = 2013).

double powered = Math.Pow(y, i);

Here, you don't have to try all exponentiations from exponents 2 to 9. There's many other ways to check if an integer is a power of another.

if (x % y == 0 && powered == x && x % 10 != 0)

Modulo have a cost and here, it's useless, since you already computed the computation of the power and if powered == x the "is divisible by" check is pointless. Also, I don't understand the x % 10, some expected results are divisible by 10 (check a32 above).


Where your code become slow is that you check for all numbers until you reach the expected results count.

Instead of checking for all of these iterations if the sum of digits can be powered to reach the current iteration, let's take the problem in another side.

Let's try, only all the powered bases from 7 to 100 (arbitrary values that that match possibles representations) and check if the sum of its digits match the base. So, we only test number that are a nth power. Place all these results in a list that you sort to get the real order.

Here, for demonstration purpose, I used a struct embedding all info about results, but you can also just use a List and store the number part.

(note that I'm not a c# guru, there's surely some improvements possibles)

using System;
using System.Collections.Generic;

public class Program
{
    private const int MinRadix = 7;
    private const int MaxRadix = 100;
    private static List<Result> results = new List<Result>();

    public struct Result
    {
        public long number;
        public long radix;
        public long exp;
    }

    public static void Main(string[] args)
    {
        ComputeResults();
        SortResults();
        PrintResults();
    }

    private static long SumOfDigits(long value)
    {
        long sum = 0;
        while (value > 0)
        {
            sum += value % 10; 
            value /= 10; 
        }
        return sum;
    }

    private static void ComputeResults()
    {
        int count = 0;
        for (long radix = MinRadix; radix <= MaxRadix; ++radix)
        {
            int exp = 1;
            var current = radix;

            while (current < long.MaxValue / radix)
            {
                ++exp; 
                current *= radix;

                if (radix == SumOfDigits(current)) {
                    Result result = new Result();
                    result.number = current;
                    result.radix = radix;
                    result.exp = exp;
                    results.Add(result);
                    ++count;
                }               
            }
        }
    }

    private static void SortResults()
    {
        results.Sort((x, y) => x.number.CompareTo(y.number));
    }

    private static void PrintResults()
    {
        for (int i = 0; i < results.Count; i++)
        {
            Console.WriteLine($"{i+1}: {results[i].number} = {results[i].radix} ^ {results[i].exp}");   
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Good answer. The only thing to add is with respect to "(arbitrary values that that match possibles representations)": with a bit of care the arbitrariness can be eliminated. The hint I'd give OP is to use a priority queue. \$\endgroup\$ – Peter Taylor Dec 12 '18 at 10:03
  • \$\begingroup\$ @PeterTaylor I just did some little improvements \$\endgroup\$ – Calak Dec 12 '18 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.