Project Euler : 52

125874 * 2 = 251748
125874 and 251748 are permuted, bcoz these two numbers contain same digits.

How can we check that, two numbers r permutation of each other or not ?

A simple algorithm would be,
split those two numbers in an array
sort them
and compare

splitting a number can be done either continuously MOD the number with 10
then divide it with 10 and assigned the result to itself

while ( number ) {
digit [ k++ ] = number % 10;
number /= 10;
}

now sort the array, and compare
it two arrays r equal then they r permutation of each other

or, u can use string.
Here is a sample code to check permutation.

#include "stdio.h"
#include "algorithm"
#include "string.h"
using namespace std;

int main ()
{
	char a [15], b [15];

	printf ("Enter First Number: ");
	scanf ("%s", a);

	printf ("Enter Second Number: ");
	scanf ("%s", b);

	sort ( a, a + strlen ( a ) );
	sort ( b, b + strlen ( b ) );

	if ( strcmp ( a, b ) == 0 )
		printf ("Permutation\n");
	else
		printf ("Not a Permutation\n");

	return 0;
}

Ranges : (our required ans. Would be … )
Below 100 :: the ans. Must not exist here
Below 1000 :: 100 – 166
Below 10000 :: 1000 – 1666
Below 100000 :: 10000 – 16666
Below 1000000 :: 100000 – 166666

Interestingly the final ans is a permutation of the two numbers which r given in sample examples.

Project Euler : 35

Circular prime: (above 100 and below 1000)
113 (131, 311)
131 (311, 113)
197 (971, 719)
199 (991, 919)
311 (113, 131)
337 (373, 733)
373 (733, 337)
719
733
919
971
991
u just need to check the circular rotation not permutation …

sieve algorithm to save prime up to 1 million and then test whether it is circular prime

or, first check primality then justify circular or not
// dissect an integer number
i = 1
continue while (Number not equals to zero) {
array [ i ] = Number MOD 10
Number = Number / 10
i++
}
reverse the array
// there is no easy way to gain success and respect !!

u can easily discard those numbers which contain digits 0, 2, 4, 5, 6, 8.
tho, 23 is a prime number but when we make a circular rotation then it turns to 32. similarly, when any prime numbers contains 0, 2, 4, 5, 6, 8 then their circular rotation must not prime.

[resources r taken from Euler thread]

http://home.comcast.net/~babdulbaki/Circular_Primes.html

http://primes.utm.edu/glossary/page.php?sort=CircularPrime

Project Euler : 21

We have to evaluate the sum of all the amicable numbers under 10000
what if, A < 10000 but B > 10000 ?
should we consider such situation ?
can this case happen ever ?
Hmm … who knows ?

Algorithm 1: [Collected from Euler thread]
continue ( a = 2 to 9999) : a++ {
b = sum_of_proper_divisors (a)
if (b > a) and (sum_of_proper_divisors (b) is equals to a) then
Sum += (a + b)
}

// A function / method to find sum_of_proper_divisors (x)

continue ( n = 1 to x/2) : n++ {
if (x MOD n is equals to 0) then
Sum += n
}

// Odd numbers can’t have Even numbers of divisors.
// Even numbers can have Odd numbers of divisors.

Pairs :
220 284
…. ….
2620 2924
…. ….
6232 6368

useful sites:
integer sequence
amicable numbers

Project Euler : 18

Data type:
integer

Process:
Lets discuss the triangle below
3
7 5
2 4 6
8 5 9 3
it is left justified, actual indentation is given in question.
Each time u have to start from 3
now, we have two different paths, either choose 7 or 5
let, we choose 5
3
7 5
2 4 6
8 5 9 3
After choosing 5, we have two options again, either 4 or 6
let, we choose 4
3
7 5
2 4 6
8 5 9 3
After choosing 4, either 5 or 9
3
7 5
2 4 6
8 5 9 3
now, if we choose 5 then, 3 + 5 + 4 + 5 = 17
or, if we choose 9 then, 3 + 5 + 4 + 9 = 21

There r total 8 paths in this triangle,
3 + 7 + 2 + 8 = 20
3 + 7 + 2 + 5 = 17
3 + 7 + 4 + 5 = 19
3 + 7 + 4 + 9 = 23 (MAX)
3 + 5 + 4 + 5 = 17
3 + 5 + 4 + 9 = 21
3 + 5 + 6 + 9 = 23 (MAX)
3 + 5 + 6 + 3 = 17

There r 16384 routs in given triangle, the triangle we have to work with. So, brute force can be applied. You can check all the routs to find the maximum total.

// An efficient method [Also applicable for problem 67]

3
7 5
2 4 6
8 5 9 3
after 2, we can select either 8 or 5
as we r searching the max total, so we’ll take 8
add 8 and 2, and replace 2 with the result
8 + 2 = 10
3
7 5
10 4 6
8 5 9 3
now, consider 4
3
7 5
2 4 6
8 5 9 3
after 4, either 5 or 9, finding the max, it’ll be 9
so, 9 + 4 = 13
3
7 5
10 13 6
8 5 9 3
consider 6 and similarly
3
7 5
10 13 15
8 5 9 3
consider 7,
3
7 5
10 13 15
8 5 9 3
it will look like,
3
20 5
10 13 15
8 5 9 3
consider 5,
3
20 20
10 13 15
8 5 9 3
consider 3,
both ways, it will be 23.

DP solution

Project Euler : 15

Using Pascal triangle:

Solution 1 :
Pascal triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

for 1 * 1 grid : 2
for 2 * 2 grid : 6
for 3 * 3 grid : 20

Solution 2 :
1
1 1 ➡ 1 + 1 = 2
1 2 1 ➡ 1 + 2² + 1 = 6
1 3 3 1 ➡ 1 + 3² + 3² + 1 = 20
1 4 6 4 1 ➡ 1 + 4² + 6² + 4² + 1 = 70

Solution 3:
Combination:
N C R = N ! / ( R! * (N – R) ! )
Here, R = Number of Rows
N = R + R

Solution 4:
Catalan:

Solution 5:
Given a sample solution of 4 * 4 grid.

Solution 6:
There is a sequence of this set of numbers
for 4 * 4 grid = 70
for 5 * 5 grid = 252
for 6 * 6 grid = 924
for 7 * 7 grid = 3432

Shortest path diagram
for 1 * 1 to 5 * 5

[These resources are taken from Euler thread]

Project Euler: 48

Data type:
integer

Source Code:
Following code will print ( Number ^ Number )
This code is written based on Big integer in array
The value of ‘Number’ shouldn’t cross 1000.

Source code (Number ^ Number) in C

Declare a 2-D array Value [1000][12]
Column number is 12 bcoz, u need just last 10 digits.
u r just three digits behind.

1^1											1
2^2											4
3^3										2	7
4^4									2	5	6
5^5								3	1	2	5
6^6							4	6	6	5	6
7^7						8	2	3	5	4	3
8^8				1	6	7	7	7	2	1	6
9^9			3	8	7	4	2	0	4	8	9
10^10	…	0	0	0	0	0	0	0	0	0	0
11^11	…	5	3	1	1	6	7	0	6	1	1
12^12	…	6	1	0	0	4	4	8	2	5	6
…	…	…	…	…	…	…	…	…	…	…	…
1000^1000	…	0	0	0	0	0	0	0	0	0	0
Add (+)	…	9	1	1	?	?	?	6	7	0	0

Project Euler: 25

Data type:
integer

Source:
The first term in the Fibonacci sequence to contain 1000 digits is:

107006626638275893676498058445739688508368389663215166501323520
337531452060469404062188914758248979265780469488817759195748433
646667256995951299603046126274809248218614406943305123477444275
027378175308757939166619214925918675955396642283714894311307469
950343954700198543260972306729019287052644724372611771582182554
849112052501320147861296593138179223555965745203950613755146783
754322911960212993404826070617539770684706820289548690266618543
512452190036948064135744747091170761976694569107009802439343961
747410373691250323136553216477369702316775505159517351846057995
491941096777837322966579658164651390348815425631018422419025984
608800011018625555024549393711365165703944762958471454852342595
042858242530608354443542821261100899286379504800689433030977321
783486454311320576565986845628861680871869383529735064398629764
066000072356291790520705116407761481249188583094594056668833910
935094445657635766615161931775379289166158132715961687748798382
1820492520348473874384736771934512787029218636250627816

I solved this problem using big integer in array

actually I think there is a sequence of increasing terms in Fibonacci number, if u find the sequence then it's more easy than above one.
tho I didn't understand and not sure about the existence of such sequence.

Fibonacci table.

Project Euler: 14

Data type:
double / unsigned long integer

Algorithm:
Count = 1
Continue until (Number not equals to 1) {
if (Number even) then, Number /= 2
else, 3 * Number + 1
Count++
}

similar problem,
ACM problem no: 100
ACM problem no: 371 (not so similar but… yea)
ACM problem no: 694

below 1 million … (the required number) produces the longest sequences of 525 terms

A really cool site, lets have a look at it.

Project Euler: 20

Data type:
Integer

There is nothing new to tell.
Take help from Project Euler: 16 post (Under Euler: 11 to 20 category) and Big integer in array (Under Common category)

100 ! = 9332621544394415268169923885626
67004907159682643816214685929638952175
99993229915608941463976156518286253697
92082722375825118521091686400000000000
0000000000000

Shortcut would be troublesome in long run.
There r various paths. Choose ur one.

Project Euler: 16

Data type:
Integer

Logic:
Follow “Big integer in Array” under Common Categories. Array size 500 enough.
2 * 2 * 2 * 2 * 2 * 2 * ….(total number of 2 is 1000) = 2 ^ 1000

// 2 ^ 100 = 1267650600228229401496703205376

// Using Python, Mathematica, PHP, Ruby … u can solve this problem in a minute.

// I have found another process to solve the problem in Euler thread, it is all abt recursion and unfortunately I'm not very good at it, so let me understand and analyze the process first then I wish to publish here may be.