MathsLab

Prime factorization of n!

2013-05-01T12:59:00.000+05:30

Rather than the conventional ways of prime factorization, there is an easy way to do the prime factorization of n!. First of all you have to list out all the prime numbers less than or equal to n. It is because

n! = 1 x 2 x 3 x 4 x 5 x .... x n

So prime factors of n! are all the prime numbers less than n. Next we have to find out the multiplicity of each of these prime factors.

In the prime factorization, for example,

60 = 2 x 2 x 3 x 5

the multiplicity of the prime factor 2 is 2, while the multiplicity of each of the prime factors 3 and 5 is 1. Thus, 60 has 4 prime factors, but only 3 distinct prime factors.

Now, if m is the largest prime number less than or equal to n,

n! = 2^m1 x 3^m2 x ... x m^p

Now we have to find out these multiplicities m1, m2, ..... ,p of prime factors.

Let’s take an example of 10!

Prime numbers less than 10 are 2,3,5,7

10! = 2^m1 x 3^m2 x 5^m3 x 7

We already know there will one prime factor of 7 in 10! (1 x 2 x ... x 7 x... x 10).

We have to find m1, m2 and m3 corresponding to 2, 3 and 5.

There are five multiples of 2 between 1 and 10.

2 x 1 , 2 x 2 , 2 x 3 , 2 x 4 , 2 x 5

There are two multiples of 2 between 1 and 5.

2 x 1, 2 x 2

There is only one multiple of 2 between 1 and 2.

2 x 1

Thus multiplicity of the prime factor 2 is m1 = 5 + 2 + 1 = 8.

Similarly,

There are three multiples of 3 between 1 and 10.

3 x 1 , 3 x 2 , 3 x 3

There is only one multiple of 3 between 1 and 3.

3 x 1

Thus multiplicity of the prime factor 3 is m2 = 3 + 1 = 4.

Similarly,

There are two multiples of 5 between 1 and 10.

5 x 1 , 5 x 2

Thus multiplicity of the prime factor 5 is m3 = 2.

So the prime factorization of 10! is as follows

10! = 2⁸ x 3⁴ x 5² x 7

Once you get the idea, its easier to do the prime factorization of factorials.

Google doodle for Srinivasa Ramanujan's 125th birthday

2012-12-22T11:12:00.002+05:30

Srinivasa Ramanujan's 125th birthday marked by Google India doodle on 22 December 2012.

Srinivasa Ramanujan was an Indian mathematician and autodidact who, with almost no formal training in pure mathematics, made extraordinary contributions to mathematical analysis, number theory, infinite series, and continued fractions.

December 22nd is the National Mathematics Day in India.

See also : http://themathslab.blogspot.in/2012/08/story-of-1729-first-taxicab-number.html

Locker puzzle

2012-08-29T10:48:00.001+05:30

1. A high school has a strange principal. On the first day, he has his students perform an odd opening day ceremony:
There are one thousand lockers and one thousand students in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open?

Number Patterns

2012-08-24T18:41:00.000+05:30

Some amazing number patterns:

1 x 1 = 1

11 x 11 = 1 2 1

111 x 111 = 1 2 3 2 1

1111 x 1111 = 1 2 3 4 3 2 1

11111 x 11111 = 1 2 3 4 5 4 3 2 1

111111 x 111111 = 1 2 3 4 5 6 5 4 3 2 1

1111111 x 1111111 = 1 2 3 4 5 6 7 6 5 4 3 2 1

11111111 x 11111111 = 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1

111111111 x 111111111 = 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1

0 x 9 + 1 = 1

1 x 9 + 2 = 1 1

1 2 x 9 + 3 = 1 1 1

1 2 3 x 9 + 4 = 1 1 1 1

1 2 3 4 x 9 + 5 = 1 1 1 1 1

1 2 3 4 5 x 9 + 6 = 1 1 1 1 1 1

1 2 3 4 5 6 x 9 + 7 = 1 1 1 1 1 1 1

1 2 3 4 5 6 7 x 9 + 8 = 1 1 1 1 1 1 1 1

1 2 3 4 5 6 7 8 x 9 + 9 = 1 1 1 1 1 1 1 1 1

0 x 9 + 8 = 8

9 x 9 + 7 = 8 8

9 8 x 9 + 6 = 8 8 8

9 8 7 x 9 + 5 = 8 8 8 8

9 8 7 6 x 9 + 4 = 8 8 8 8 8

9 8 7 6 5 x 9 + 3 = 8 8 8 8 8 8

9 8 7 6 5 4 x 9 + 2 = 8 8 8 8 8 8 8

9 8 7 6 5 4 3 x 9 + 1 = 8 8 8 8 8 8 8 8

9 8 7 6 5 4 3 2 x 9 + 0 = 8 8 8 8 8 8 8 8 8

9 1 x 3 7 = 3 3 6 7

9 9 0 1 x 3 3 6 7 = 3 3 3 3 6 6 6 7

9 9 9 0 0 1 x 3 3 3 6 6 7 = 3 3 3 3 3 3 6 6 6 6 6 7

9 9 9 9 0 0 0 1 x 3 3 3 3 6 6 6 7 = 3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 7

4² = 16

34² = 1156

334² = 111556

3334² = 11115556

33334² = 1111155556

333334² = 111111555556

3333334² = 11111115555556

33333334² = 1111111155555556

333333334² = 111111111555555556

3333333334² = 11111111115555555556

7² = 49

67² = 4489

667² = 444889

6667² = 44448889

66667² = 4444488889

666667² = 444444888889

6666667² = 44444448888889

66666667² = 4444444488888889

666666667² = 444444444888888889

6666666667² = 44444444448888888889

1 + 2 = 3
4 + 5 + 6 = 7 + 8
9 + 10 + 11 + 12 = 13 + 14 + 15
16 + 17 + 18 + 19 + 20 = 21 + 22 + 23 + 24
25 + 26 + 27 + 28 + 29 + 30 = 31 + 32 + 33 + 34 + 35
36 + 37 + 38 + 39 + 40 + 41 + 42 = 43 + 44 + 45 + 46 + 47 + 48
49 + 50 + 51 + 52 + 53 + 54 + 55 + 56 = 57 + 58 + 59 + 60 + 61 + 62 + 63

Story of 1729 : The first taxicab number

2012-08-24T00:33:00.000+05:30

1729 is known as the Hardy–Ramanujan number after a famous anecdote of the British mathematician G. H. Hardy regarding a hospital visit to the Indian mathematician Srinivasa Ramanujan. In Hardy's words:

I remember once going to see him when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavorable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."

G. H. Hardy and Srinivasa Ramanujan

The two different ways are these:

1729 = 1³ + 12³ = 9³ + 10³

Generalizations of this idea have created the notion of "taxicab numbers" ( The nth taxicab number Ta(n) is the smallest number representable in n ways as a sum of positive cubes).
The number was also found in one of Ramanujan's notebooks dated years before the incident, and was noted by Frénicle de Bessyin 1657.

Some of the other notable features of 1729 are:

The same expression defines 1729 as the first in the sequence of "Fermat near misses" defined as numbers of the form 1 + z³ which are also expressible as the sum of two other cubes.

1729 is also the third Carmichael number and the first absolute Euler pseudo-prime. It is also a sphenic number.

1729 is a Zeisel number. It is a centered cube number, as well as a dodecagonal number, a 24-gonal and 84-gonal number.

Investigating pairs of distinct integer-valued quadratic forms that represent every integer the same number of times, Schiemann found that such quadratic forms must be in four or more variables, and the least possible discriminant of a four-variable pair is 1729.

Because in base 10 the number 1729 is divisible by the sum of its digits, it is a Harshad number. It also has this property in octal (1729 = 3301₈, 3 + 3 + 0 + 1 = 7) and hexadecimal(1729 = 6C1₁₆, 6 + C + 1 = 19₁₀), but not in binary.

1729 has another mildly interesting property: the 1729th decimal place is the beginning of the first occurrence of all ten digits consecutively in the decimal representation of the transcendental number e.

Masahiko Fujiwara showed that 1729 is one of four positive integers (with the others being 81, 1458, and the trivial case 1) which, when its digits are added together, produces a sum which, when multiplied by its reversal, yields the original number:

1 + 7 + 2 + 9 = 19

19 × 91 = 1729.

The physicist Richard Feynman demonstrated his abilities at mental calculation when, during a trip to Brazil, he was challenged to a calculating contest against an experienced abacist. The abacist happened to challenge Feynman to compute the cube root of 1729.03; since Feynman knew that 1729 was equal to 12³+1 (because one cubic foot equals 1728 cubic inches), he was able to compute by hand an accurate value for its cube root using interpolation techniques (specifically, binomial expansion). The abacist had to solve the problem by a more laborious algorithmic method, and lost the competition to Feynman. The anecdote is related by Feynman in his memoir, Surely You're Joking, Mr. Feynman!.

The Prince Of Mathematics

2012-08-23T17:42:00.000+05:30

Carl Friedrich Gauss

In 1787 at a german school, the schoolmaster gave the following assignment to his students: "Write down all the whole numbers from 1 to 100 and add up their sum". After finishing the assignment, each student has to bring his slate forward and place it on the schoolmaster's desk. The teacher expected the beginner's class to take a good while to finish this exercise. But in a few seconds, to his teacher's surprise, a student proceeded to the front of the room and placed his slate on the desk. The schoolmaster was astounded to see only one number: 5050 in that student's slate. That boy then had to explain to his teacher that he found the result because he could see that, 1+100=101, 2+99=101, 3+98=101, so that he could find 50 pairs of numbers that each add up to 101. Thus, 50 times 101 will equal 5,050.

That 10-year-old boy genius was 'Carl Friedrich Gauss' who later became one of the greatest mathematicians in the world history and the world called him 'The Prince of Mathematics'.

Carl Friedrich Gauss (1777-1855) is considered to be the greatest German mathematician of the nineteenth century. His discoveries and writings influenced and left a lasting mark in the areas of number theory, astronomy, geodesy, and physics, particularly the study of electromagnetism.

Gauss was born in Brunswick, Germany, on April 30, 1777, to poor, working-class parents. His father labored as a gardener and brick-layer and was regarded as an upright, honest man. However, he was a harsh parent who discouraged his young son from attending school, with expectations that he would follow one of the family trades. Luckily, Gauss' mother and uncle, Friedrich, recognized Carl's genius early on and knew that he must develop this gifted intelligence with education.

At the age of fourteen, Gauss was able to continue his education with the help of Carl Wilhelm Ferdinand, Duke of Brunswick. After meeting Gauss, the Duke was so impressed by the gifted student with the photographic memory that he pledged his financial support to help him continue his studies at Caroline College. At the end of his college years, Gauss made a tremendous discovery that, up to this time, mathematicians had believed was impossible. He found that a regular polygon with 17 sides could be drawn using just a compass and straight edge. Gauss was so happy about and proud of his discovery that he gave up his intention to study languages and turned to mathematics.

Duke Ferdinand continued to financially support his young friend as Gauss pursued his studies at the University of Gottingen. While there he submitted a proof that every algebraic equation has at least one root or solution. This theorem had challenged mathematicians for centuries and is called "the fundamental theorem of algebra".

Gauss' next discovery was in a totally different area of mathematics. In 1801, astronomers had discovered what they thought was a planet, which they named Ceres. They eventually lost sight of Ceres but their observations were communicated to Gauss. He then calculated its exact position, so that it was easily rediscovered. He also worked on a new method for determining the orbits of new asteroids. Eventually these discoveries led to Gauss' appointment as professor of mathematics and director of the observatory at Gottingen, where he remained in his official position until his death on February 23, 1855.

Carl Friedrich Gauss, though he devoted his life to mathematics, kept his ideas, problems, and solutions in private diaries. He refused to publish theories that were not finished and perfect. Still, he is considered, along with Archimedes and Newton, to be one of the three greatest mathematicians who ever lived.