# Palindromes

Standard

What is a Palindrome?
A palindrome is a word, which reads backwards the same as it does forwards. Well known examples are Anna or radar.
You can apply this principle to numbers. For instance 1001 or 69896 are palindromes.

Counting the Palindromes
All the digits are palindromes (1,2,3,…,9).

There are also 9 palindromes with two digits (11,22,33, …,99).

You can find to every two-digit number one, and only one number with three digits and with four digits.
For example: For the number 34 there are 343 and 3443.
You can conclude that there are 90 palindromes with three and also 90 palindromes with four digits.

You can find to every three-digit number one, and only one number with five digits and with six digits.
For example: To the number 562 there are 56265 and 562265.
You can conclude that there are 900 palindromes with five and 900 palindromes with six digits.

You have 9+9+90+90+900+900 = 1998 palindromes up to one million. That’s 0,1998 %. About every 500th number is a palindrome.

Position of the Palindromes
But they are not spread over all numbers regularly. This shows the picture below, which includes the first 1000 numbers.

Products with the Digit 1
11×11 = 121
111×111 = 12321
1111×1111 = 1234321

111 111 111 x 111 111 111=12345678987654321

again…

11×111 = 1221
111×1111 = 123321
1 111×11111 = 12344321

111 111 111 x 1 111 111 111=123456789987654321

I suppose that all products with the digit 1 are palindromes, if one.factor has at the most 9 digits.
All palindromes have the shape 123…..321.

Prime Numbers among the Palindromes
All palindromic primes with 3 digits:

 101 131 151 181 191 313 353 373 383 . 727 757 787 797 . 919 929 . . .

There are no primes with 4 digits. They all have the factor 11. (Example:4554=4004+550=4×1001+550=4x91x11+11×50=11x(4×91+50)
There are 93 primes with 5 digits.
There are no primes with 6 digits. They all have the factor 11.
There are 668 primes with 7 digits.

196-Problem
Pick a number. Add the number, which you must read from the right to the left (mirror number), to the original number. Maybe the sum is a palindrome. If the sum isn’t a palindrome, add the mirror number of the sum to the sum. Maybe you have a palindrome now, otherwise repeat the process. Nearly all numbers have a palindrome in the end.
Example: 49       49+94=143       143+341= 484 !
There are some numbers, which have no palindromes. The lowest one is 196. But the proof is still missing.

# Project Euler Problem No.5

Standard

Consider the numbers you have to test:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Break up the composite numbers to prime factors:
1, 2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5,
11, 2*2*3, 13, 2*7, 3*5, 2*2*2*2, 17, 2*3*3, 19, 2*2*5

For a number to be divisible by each of these groups, they have to show up among the prime factorization of our number.

The smallest number divisible by 1, 2, and 3 is 1*2*3 = 6.
To find the smallest number divisible by 1, 2, 3 and 4, we don’t have to multiply all of them together because there’s some redundancies. (2,2,3) is the smallest set that includes the sets (2), (3) and (2,2). So 2*2*3 = 12 is the smallest number divisible by 2, 3 and 4.

There are no 5s in the set (2,2,3), so the first number divisible by 1 through 5 has to be (2,2,3,5) = 60.

6 is 2*3, and we already have that, so we’ve found the number divisible by 1 through 6. Since 7 is prime, our new number has to be (2,2,3,5,7) = 420 in order to be divisible by everything up through 7.

8 is 2*2*2, so in order for (2,2,2) to be a subset we need to add one more two to get (2,2,2,3,5,7).

Continue on like this to get (2,2,2,3,3,5,7) for 9, which is already set for 10=2*5. 11 is prime, so we have (2,2,2,3,3,5,7,11). We’re all set for 12, because 12=2*2*3 and we have two 2s and a 3. For 13 we need (2, 2, 2, 3, 3, 5, 7, 11, 13). This already includes the factors of 14=2*7 and 15=3*5. For 16 we need an extra 2, to get (2, 2, 2, 2, 3, 3, 5, 7, 11, 13).

Then to 17: (2, 2, 2, 2, 3, 3, 5, 7, 11, 13). 18 is all set. 19 makes it (2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 19). And 20 is all set because we already have (2,2,5).

So the shortest number is
2*2*2*2 * 3*3 * 5*7*11*13*19 = 1,3693,680

# Fermat number

Standard

Pierre de Fermat wrote to Marin Mersenne on December 25, 1640 that:
If I can determine the basic reason why
3, 5, 17, 257, 65 537, …,
are prime numbers, I feel that I would find very interesting results, for I have already found marvelous things [along these lines] which I will tell you about later. [Archibald1914].
This is usually taken to be the conjecture that every number of the form is prime. So we call these the Fermat numbers, and when a number of this form is prime, we call it a Fermat prime.
The only known Fermat primes are the first five Fermat numbers: F0=3, F1=5, F2=17, F3=257, and F4=65537. A simple heuristic shows that it is likely that these are the only Fermat primes (though many folks like Eisentsein thought otherwise).

In 1732 Euler discovered 641 divides F5. It only takes two trial divisions to find this factor because Euler showed that every divisor of a Fermat number Fn with n greater than 2 has the form k.2n+2+1. In the case of F5 this is 128k+1, so we would try 257 and 641 (129, 385, and 513 are not prime). Now we know that all of the Fermat numbers are composite for the other n less than 31. The quickest way to check a Fermat number for primality (if trial division fails to find a small factor) is to use Pepin’s test.

Gauss proved that a regular polygon of n sides can be inscribed in a circle with Euclidean methods (e.g., by straightedge and compass) if and only if n is a power of two times a product of distinct Fermat primes.

The Fermat numbers are pairwise relatively prime, as can be seen in the following identity:

F0F1F2…..Fn-1 +2 = Fn.
(This gives a simple proof that there are infinitely many primes.)
The quickest way to find out if a Fermat number is prime, is to use Pepin’s test [Pepin77]. It is not yet known if there are infinitely many Fermat primes, but it seems likely that there are not.