Hablu

Standard

My first experience of problem setting. It feels good when you see people think about your problem and come up with better solutions than yours 😛
This problem is about math and primes. The link is this.

Project Euler Problem : 48

Standard

The problem statement says

The series, 1^(1) + 2^(2) + 3^(3) + … + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + … + 1000^(1000).

Though seems like it can’t be solved without using bignumber(in c/c++), The bignumber solution takes much more time than we can say moderate for a computer program(same in JAVA). Actually it needs some modular operations. You need the last ten digits and to calculate them you don’t need to calculate all the digits. See my approach

#include <stdio.h>

long long power(int a);

int main()
{
	int i;
	long long ans=0;
	
	for(i=1; i<=1000; i++)
	{
		ans=(ans+power(i))%10000000000000;
	}
	
	ans=(ans%10000000000);
	
	printf("%lld\n",ans);
	
	return 0;
}

long long power(int a)
{
	int i;
	long long ans=1;
	
	for(i=1; i<=a; i++)
	{
		ans*=a;
		ans=ans%10000000000000;
	}
	
	return ans;
}

Fractals

Standard





Fractal? What’s That?

A point has dimension 0, a line has dimension 1, and a plane has dimension 2. But did you know that some objects can be regarded to have “fractional” dimension?

You can think of dimension of an object X as the amount of information necessary to specify the position of a point in X. For instance, a block of wood is 3-dimensional because you need three coordinates to specify any point inside.

Fractal

The Fractal ( Cantor set ) has fractional dimension! Why? Well it is at most 1-dimensional, because one coordinate would certainly specify where a point is. However, you can get away with “less”, because the object is self-similar.

In Mathworld Fractals are defined as

an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales.
This is a fancy way of saying that a fractal is a geometrical figure that has fractional dimension (non integer) including the same pattern, scaled down and rotated, and repeated over and over.
If you still can’t visualize the aspect ( just like almost every first timers ) just peek here.

Fractal

Fractals are said to have a unique property named self similarity. We see the same image again when we “zoom” in and examine a portion of the original.





How Everything Started

Gaston Julia(1893-1978) was a French mathematician who published a book on the iteration of rational functions in 1918. Before computers, he had to draw the sets of functions by hand. These types of fractals are now called Julia sets. His masterpiece on these sets was published in 1918. His interest apparently was piqued by the 1879 paper by Sir Arthur Cayley called The Newton-Fourier Imaginary Problem.

Broccoli fractal

Benoit Mandelbrot (1924- ) is an emeritus professor at Yale University. He used a computer to explore Julia’s iterated functions, and found a simpler equation that included all the Julia sets. Mandelbrot set is named after him.

Waclaw Sierpinski (1882-1969) was a Polish mathematician. His work predated Mandelbrot’s discovery

of fractals. He is known for the Sierpinski triangle, but there are many other Sierpinski-style fractals.

Coastline fractal

In 1918, Bertrand Russell had recognised a “supreme beauty” within the mathematics of fractals that was then emerging. The idea of self-similar curves was taken further by Paul Pierre Levy, who, in his 1938 paper Plane or Space Curves and Surfaces Consisting of Parts Similar to the Whole described a new fractal curve, the Levy C curve. Georg Cantor also gave examples of subsets of the real line with unusual properties – these Cantor sets are also now recognized as fractals.





Properties of Fractals

The essential and most fascinating property of any fractal is its non integer dimension and complexity. The rule for

Snow flake fractal

creating one is essentially simple – A-Level mathematics no more. But the resulting picture has suprising depth. If you zoom in on any part of a fractal, you find the same amount of detail as before. It does not simplify. You find echoes of larger shapes appearing within smaller parts of the shape.

If you zoom in further, the same thing happens. You never seem to get down to the skeleton of the picture, just detail upon detail. Look here or here for illustrations of this. There are many computer programs available for you to do this yourself.
Fractint is probably the best. It is freely available here.





Fractals in Life, Nature or may be beyond that

Coastline fractal in midwest USA

Nature is full of fractals. From a tiny Broccoli, crystals, peacock tail to clouds, snow flakes and blood vessels, approximate fractals are easily found in nature.

Butterfly Effect


Sea shell, urchin,thunder ightnings are also fractals. The Coastline fractal in midwest USA is a surprising example of them as well.

The Butterfly Effect is most succesfully explained by Fractals.

Even the internet (world wide web) is fractal leading us to great links having medium sized links and furthur.
Learn more about fractal nature of internet here.

Butterfly Effect

According to this the universe isformed in a fractal structure, and our cosmos might be a particle, too.
We might be living in a particle. Such particles as the cosmos may exist innumerably.
And there might be a gigantic universe, and it is not the end of all there is. In fact, it might be another particle in another greater universe.

Euler’s Totient Theorem

Standard

Now I will present a wonderful fact about the coprimes to n — they form a group under multiplication mod n, which leads to:

If GCD(a,n) = 1 then aφ(n) = 1 (mod n).

Proof: take a to be any positive integer coprime to n.
Let A be the set of numbers coprime to n: A = {a1, a2, a3, …, aφ(n)}
Let aA be the product of the number, a, with each of the elements of A: aA = {aa1, aa2, aa3, …, aaφ(n)}
No two elements of aA are congruent mod n (see lemma 1, below*), so their residues mod n must be {a1, a2, a3, …, aφ(n)} in some order.
By equating the product of the numbers in set aA with the product of those in set A, mod n,
aφ(n)a1a2a3…aφ(n) = a1a2a3…aφ(n) (mod n)
Since a1a2a3…aφ(n) is coprime to n, we can divide both sides by a1a2a3…aφ(n), mod n, proving Euler’s Totient Theorem.

* Lemma 1: Why are no two elements of aA = {aa1, aa2, aa3, …, aaφ(n)} congruent, mod n?
Suppose a is a number coprime to n, and b and c are two different numbers, also coprime to n, in the range [1,n-1] and ab=ac, mod n.
Then ab-ac=nk, where k is an integer.
a(b-c)=nk, and since b-c is smaller than n in absolute value, a must be larger than k in absolute value.
a and n have no factors in common, so a|k, but a can’t divide k, since a is larger than k, a contradiction.


Other Totient Theorems

Let’s write m = 2n-1 for convenience.
Now 2n = m+1, so 2n = 1 (mod m), but no smaller (but still positive) power of 2 is equivalent to 1 (mod m).
So (2n)k = 1 (mod m), which means 2kn = 1 (mod m) for any integer, k.
2φ(m) = 1 (mod m), by Euler’s Totient Theorem.
We can divide φ(m) by n giving quotient q and remainder r such that φ(m) = qn+r, and so
2φ(m) = 2qn+r = 2qn 2r = 1 (mod m), and we know 2qn = 1 (mod m), so 2r = 1 (mod m), and 0 ≤ r < n, so r=0

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