Euler Problem 108:

gdje su: x,y,n>0 prirodni brojevi.

Prije bilo kakvog zaključka potrebno je početnu jednačinu transformirati u drugi oblik. Gornju jednakost možemo napisati:

Dodajmo lijevoj i desnoj strani , pa imamo:

Sada naša jednačina ima drugačiji smisao, odnosno pojednostavljeno rješenje, a to je: Potrebno je pronaći za koje , ima broj divizora koji prelaze 2x.

Rješenje se najbrže može pronaći korištenjem Wolfram Mathematica i to:

For[i = 2, i != 1, i++, If[DivisorSigma[0, i^2] > 2000, Break[]]]; i

Ovo je jednostavniji oblik problema 110, koji traži broj rješenja koji prelaze 4.000.000. Svakako da pristup koji je prezentiran nije adekvatan. S toga je potrebno ovaj problem proširiti. Zadnjom jednačinom pokazali smo da je potrebno pronaći broj čiji kvadrat treba da ima određen broj divizora. Osnovni teorem Aritmetike kaže svaki prirodni broj se može jedinstveno napisati u obliku produkta prostih brojeva, odnosno:

gdje je .

S druge strane ako znamo proste faktore broja n, tada možemo izračunati broj njegovih divizora odnosno možemo izračunati sigma funkciju:

Ako je broj divizora broja dat gornjim izrazom tada broj divizora broja možemo izračunati kao:

Zadatak se svodi na rekurzivno rješavanje jednakosti:

i

Na osnovu datih izraza imamo implementaciju rješenja za probleme 108 i 110.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace EulerProblem110
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Solution PE108:{0}", Solve(1999, 1000).ToString());
            Console.WriteLine("Solution PE110:{0}", Solve(7999999, 4000000).ToString());
            Console.Read();

        }
        static BigInteger Solve(int divisors,int max,int nthPrime=0)
        {
            if(divisors<=1)
                return 1;

            else if(divisors<=3)
               return Primes().ElementAt(nthPrime);
            else
            {
                BigInteger power=Primes().ElementAt(nthPrime);
                BigInteger result=power*Solve((divisors+2)/3,1,nthPrime+1);

                for(int i=2; i<=max; ++i)
                {
                    power*=Primes().ElementAt(nthPrime);
                    if(power > result)
                        break;
                    BigInteger temp=power*Solve((divisors+2*i)/(2*i+1),i,nthPrime+1);

                    if(temp<result)
                        result=temp;
                }
                return result;
            }

		}
        static IEnumerable<long> Primes()
        {
            yield return 2;
            yield return 3;
            long prevPrime = 3;
            while (true)
            {
                prevPrime++;
                if (IsPrime(prevPrime))
                    yield return prevPrime;
            }
        }
        static bool IsPrime(long n)
        {
            if (n < 2) return false;
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
    }
}