For the past two years I've been looking at sums of primes raised to various powers and seeing what can divide them. In particular, if you sum the first n primes each raised to a power k, when is the sum divisible by n?
For example, the sum of the squares of the first 19 primes is divisible by 19:
2**2 + 3**2 + 5**2 + ... + 67**2 = 19*1314
so 19 is a solution for the second power (i.e. k = 2).
Last month I found this theorem about these divisors:
It turns out that if n does divide a power sum of primes, it will* also divide the sum of the same primes raised to a different power. In fact, there are an infinite number of powers that it will satisfy. If n divides the sum of primes to the power of k, it will also divide the sum of primes to the power of k + psi(n), where psi(n) is the Carmichael function (also known as the reduced totient function). In fact, it will divide each of the sums of primes to the power of k + i * psi(n), where i is any integer.
* as long as n is greater than or equal to the maximum power in the prime factorization of k, which is true for all the cases known in the OEIS as of today.
So if 19 is a solution for the 2nd power, it is also a solution for the 20th power as:
2 + psi(19) = 2 + 18 = 20.
Check:
2**20 + 3**20 + 5**20 + ... + 67**20 = 19*217203136831973643667990849432828422
Proof:
Given that sum i=1->n (p_i ** k) mod n = 0 (The sum is over the first n primes.)
and (i ** k) mod n = (i ** (k + psi(n))) mod n, for all integers i, if k > the maximum power in the prime factorization of n
then, sum i=1->n (p_i ** (k + j * psi(n)) mod n = sum i=1->n (p_i ** k) mod n = 0, where j is any positive integer.
Some examples:
19 is a solution for the 2nd power sum, so also a solution for the powers 20, 38, 56...
455 is a solution for the 2nd power sum, so also a solution for the powers 14, 26, 38...
The OEIS only has the solutions for the powers up to 19. 455 is the only case
where a value in the OEIS can be predicted from a sequence with a lower power. This is
because 455 has a small value of 12 for the Carmichael function.
23 is a solution for the 1st power sum, so also for the powers 23, 45, 67...
23 is a solution for the 13th power, so also for the powers 35, 57, 79...
25 is the solution to many power sums:
25 is a solution for the 3rd power sum, so also a solution for the powers 23, 43, 63...
25 is a solution for the 5th power sum, so also a solution for the powers 25, 45, 65...
25 is a solution for the 7th power sum, so also a solution for the powers 27, 47, 67...
25 is a solution for the 11th power sum, so also a solution for the powers 31, 51, 71...
25 is a solution for the 15th power sum, so also a solution for the powers 35, 55, 75...
25 is a solution for the 19th power sum, so also a solution for the powers 39, 59, 79...
Coincidentally, the first 25 prime numbers are the prime numbers up to 100. From the
above, they are a solution for every power ending in 5 (i.e. 5, 15, 25...) and half of
the powers ending in 1, 3, 7 and 9. (e.g. 11, 31, 51...)
Saturday, December 10, 2022
Saturday, May 16, 2009
Greatest Common Divisor (GCD), Least Common Multiple (LCM)
This calculator takes two numbers and finds the greatest common divisor and the least common multiple.
If you multiply the gcm by the lcd you get the same as multiplying the two original numbers.
Friday, May 1, 2009
Prime Factors Calculator
I made this javascript prime factors calculator and have found it addictive. I just keep factorizing numbers. Enter the number to factorize in the left box and click on the 'factorize' button. The prime factors are shown in the right box.
I've never had a push button prime factor generator before.
You can easily check if a number is prime. It only has one prime factor: itself.
It's easy to generate a large prime number. Just type in a long random number and get its prime factors. If one of the factors is large, you've found a large prime number. If you don't get one, try changing your random number slightly.
For example: 384339387 gives 3,37,3462517. So 3462517 is a nice large prime number.
I like adding an extra digit and seeing what factors come out:
All the numbers with an even number of ones have the factor 11. And those with 4, 8 and 12 ones have factors of 11 and 101 because 1111 = 11 X 101.
Those with an odd number of ones have only two prime factors, except 111111111 (nine ones). I wonder if there's something going on here?
Oh no, the next number lets me down: 1111111111111 has factors 53,79 and 265371653.
If you find any interesting patterns with this prime factors calculator, let me know.
I've never had a push button prime factor generator before.
You can easily check if a number is prime. It only has one prime factor: itself.
It's easy to generate a large prime number. Just type in a long random number and get its prime factors. If one of the factors is large, you've found a large prime number. If you don't get one, try changing your random number slightly.
For example: 384339387 gives 3,37,3462517. So 3462517 is a nice large prime number.
I like adding an extra digit and seeing what factors come out:
| number | prime factors |
| 11 | 11 |
| 111 | 3,37 |
| 1111 | 11,101 |
| 11111 | 41,271 |
| 111111 | 3,7,11,13,37 |
| 1111111 | 239,4649 |
| 11111111 | 11,73,101,137 |
| 111111111 | 3,3,37,333667 |
| 1111111111 | 11,41,271,9091 |
| 11111111111 | 21649,513239 |
| 111111111111 | 3,7,11,13,37,101,9901 |
All the numbers with an even number of ones have the factor 11. And those with 4, 8 and 12 ones have factors of 11 and 101 because 1111 = 11 X 101.
Those with an odd number of ones have only two prime factors, except 111111111 (nine ones). I wonder if there's something going on here?
Oh no, the next number lets me down: 1111111111111 has factors 53,79 and 265371653.
If you find any interesting patterns with this prime factors calculator, let me know.
Wednesday, April 22, 2009
The Numbers go Social Networking
Names and photos are clickable.
pythagoras image released under GNU Free Documentation License
|
Pythagoras
is thinking that a2 + b2 = c2 for right angled triangles. 12 hours ago · Comment · Like | ||||||||||||||||||||||
|
|
Complex
and
Pythagoras
are now friends. 11 hours 23i minutes ago · Comment · Like |
|
|
Pythagoras
has shared some photos. 11 hours ago · Comment · Like |
|
|
Pythagoras
is dividing a circle's circumference by its diameter. 9 hours ago · Comment · Like | ||||||||
|
|
Rational
has invited Natural to the group
Irrationality is the square root of all evil.
8½ hours ago · Comment · Like | ||
|
|
Irrational
has joined the group
Irrationality is the square root of all evil.
√59 metres ago · Comment · Like |
|
|
Pythagoras
Is zero a number? 7 hours ago · Comment · Like | ||||||||||||||||
|
|
Integer
took the quiz
What sort of Infinity are you? The answer is Countable. You are countable. You can be lined up one-to-one with the natural numbers. 4 hours ago · Comment · Like | ||
|
|
Natural
has invited
Integer,
Complex
and
Irrational
to join the group
Become more natural: square yourself
3 hours ago · Comment · Like |
|
|
Pythagoras
Anyone out there know the square root of minus one? 3 hour ago · Comment · Like | ||||||||||||||
|
|
|
Irrational
invited
Pythagoras
to join the group
Han shot first
0 microseconds ago · Comment · Like |
pythagoras image released under GNU Free Documentation License
Saturday, April 18, 2009
When are addition, subtraction, multiplication, division and exponentiation allowed?
Now that we've had a look at several groups of numbers let's bring together what operations are allowed for each one:
The complex numbers are the only group that allows addition, subtraction, multiplication and exponentiation without restriction.
These increasingly larger groups of numbers can be seen as attempts to make subtraction, division and exponentiation work without restrictions.
The natural numbers allow exponentiation without restriction, but restrict subtraction and division. We can introduce negative numbers to allow subtraction (giving us the integers), but this forces restrictions on exponentiation.
We can then introduce fractions (giving us the rational numbers) to allow almost all divisions. Then adding irrational numbers (giving us the reals) allows fractional powers of all positive numbers and some powers of negative numbers.
To finally get back to having no restrictions on exponentiation, we need to include imaginary numbers leaving us with the complex numbers.
Beyond the complex numbers are the quaternions, octonians and sedenions.
| + | - | × | ÷ | ab | |
| natural numbers | yes | only larger number minus smaller or equal number | yes | only if it divides evenly; can't divide by zero | yes |
| integers | yes | yes | yes | only if it divides evenly; can't divide by zero | only positive and zero powers |
| rational numbers | yes | yes | yes | can't divide by zero | integer powers; some fractional powers |
| real numbers | yes | yes | yes | can't divide by zero | not allow some fractional powers of negative numbers e.q. (-1)(1/2) |
| complex numbers | yes | yes | yes | can't divide by zero | yes |
These increasingly larger groups of numbers can be seen as attempts to make subtraction, division and exponentiation work without restrictions.
The natural numbers allow exponentiation without restriction, but restrict subtraction and division. We can introduce negative numbers to allow subtraction (giving us the integers), but this forces restrictions on exponentiation.
We can then introduce fractions (giving us the rational numbers) to allow almost all divisions. Then adding irrational numbers (giving us the reals) allows fractional powers of all positive numbers and some powers of negative numbers.
To finally get back to having no restrictions on exponentiation, we need to include imaginary numbers leaving us with the complex numbers.
Beyond the complex numbers are the quaternions, octonians and sedenions.
| + | - | × | ÷ | ab | |
| complex numbers | yes | yes | yes | can't divide by zero | yes |
| quaternions | yes | yes | not commutative | can't divide by zero | yes |
| octonions | yes | yes | not commutative, not associative | can't divide by zero | yes |
| sedenions | yes | yes | not commutative, not associative, not alternative | can't divide by zero | yes |
Quaternions
The quaternions are an extension of the complex numbers. Instead of having just one square root of minus one: i, why not have 3: i, j and k?
We will need a way of multiplying them together. It turns out that the following works:
ij = k = -ji
jk = i = -kj
ki = j = -ki
ijk = -1
The quaternions are not commutative, which is quite strange. The order in which you multiply them matters! If you have two quaternions, x and y, then:
x × y = - y × x
Why have 3 square roots of -1 and not 2 square roots? Because with 2 the division doesn't work properly. Why not 4, 5, 6 roots etc? Well it works with 7 roots of -1. They are called the octonians. And with 15 roots you get the sedenions. The octonians are not commutative and not associative either. The sedenions are not commutative, associative or alternative.
The quaternions are given the symbol: ℍ
We will need a way of multiplying them together. It turns out that the following works:
ij = k = -ji
jk = i = -kj
ki = j = -ki
ijk = -1
The quaternions are not commutative, which is quite strange. The order in which you multiply them matters! If you have two quaternions, x and y, then:
x × y = - y × x
Why have 3 square roots of -1 and not 2 square roots? Because with 2 the division doesn't work properly. Why not 4, 5, 6 roots etc? Well it works with 7 roots of -1. They are called the octonians. And with 15 roots you get the sedenions. The octonians are not commutative and not associative either. The sedenions are not commutative, associative or alternative.
The quaternions are given the symbol: ℍ
Complex Numbers
The complex numbers are the combination of the real numbers with the imaginary numbers. They are written as the real part plus the imaginary part. For example:
2 + 3i
The imaginary number i is defined as the square root of minus one, so i2 = -1. Multiplication of complex numbers follows the same rules as the real numbers, you just have to keep track of each part of the multiplication:
(2 + 3i) × ( 4 + 5i)
= 2 × 4 + 2 × 5i + 3i × 4 + 3i × 5i
= 8 + 10i + 12i - 15
= -7 + 22i
We can add, subtract, multiply and divide any two complex numbers and get a complex number* back (except dividing by zero). And, unlike the real numbers, we can raise any complex number to any other complex number without restriction.
For example:
32 = 9
3-2 = 1/9 = 0.11111111...
3(1/2) = √3 = 1.73205...
(-3)(1/2) = √(-3) = 1.73205i
32i = e2ln(3)i = cos(2ln(3)) + i sin(2ln(3)) = -0.5863 + 0.8101i
32+2i = 32 × 32i = 5.2763 + 7.2911i
The complex numbers are given the symbol: ℂ
-----
* the complex numbers include all real numbers. So 2 is the complex number 2 + 0i. Even though some complex multiplications give answers that are part of the real numbers, those answers are still complex numbers. For example (2 +3i) × (2 - 3i) = 13 (a real number) = 13 + 0i (a complex number).
2 + 3i
The imaginary number i is defined as the square root of minus one, so i2 = -1. Multiplication of complex numbers follows the same rules as the real numbers, you just have to keep track of each part of the multiplication:
(2 + 3i) × ( 4 + 5i)
= 2 × 4 + 2 × 5i + 3i × 4 + 3i × 5i
= 8 + 10i + 12i - 15
= -7 + 22i
We can add, subtract, multiply and divide any two complex numbers and get a complex number* back (except dividing by zero). And, unlike the real numbers, we can raise any complex number to any other complex number without restriction.
For example:
32 = 9
3-2 = 1/9 = 0.11111111...
3(1/2) = √3 = 1.73205...
(-3)(1/2) = √(-3) = 1.73205i
32i = e2ln(3)i = cos(2ln(3)) + i sin(2ln(3)) = -0.5863 + 0.8101i
32+2i = 32 × 32i = 5.2763 + 7.2911i
The complex numbers are given the symbol: ℂ
-----
* the complex numbers include all real numbers. So 2 is the complex number 2 + 0i. Even though some complex multiplications give answers that are part of the real numbers, those answers are still complex numbers. For example (2 +3i) × (2 - 3i) = 13 (a real number) = 13 + 0i (a complex number).
Subscribe to:
Posts (Atom)