Formula:
n x?i x?1 x?2 x?n
? p = p p ... p
i=1 i 1 2 n
Where:
n = the nth number in a sequence
x = a number in the sequence
p = a prime number
G[font="arial, sans-serif"]ö[/font]delization (as far as I understand) states that if you pick any natural number (x) then there is exactly one sequence of prime numbers (p) whose product (of (n) prime numbers) = x. If there are (n) numbers in the sequence, let every number be denoted by (x?1 x?2 ... x?n).
I am having trouble fully grasping this and I think it would help if someone could give me an example calculation using this formula.
I've not heard of [color=#1C2837][size=2]G[font=arial, sans-serif][size=2]ö[/font]delization, but that just looks to be the prime factorisation of an integer for which it is quite easy to prove that a) it exists, and b) that it is unique.
[color=#1C2837][size=2]
[color=#1C2837][size=2]An intuitive proof for existance would be:
let N be a number, either N is prime or it is not prime.
If it is not prime then there must exist a prime P and a possibly non-prime M (otherwise N would be prime).
[color=#1C2837][size=2]In the same way, repeat with M instead, and eventually you either get a prime number, or 1.
from which it is easy to construct a formal inductive proof.
[color=#1C2837][size=2]
[color=#1C2837][size=2]Proof of uniqueness is a little bit harder, a sketch proof would be:
Let N be the smallest integer expressible as the product of two minimal; non-identical sets of primes s1,s2..sn q1,q1...qm
[color=#1C2837][size=2]as N is the smallest such number, then s1, and s2...sn, must have unique factorisations as they are smaller than N.
[color=#1C2837][size=2]p1 then, must either divide s1, or s2...sn (or both, not important) and as all are prime, si = qj for some i,j. By removing si,qj from the two non-equal factorisations we get two smaller, equal numbers. as they are smaller than N, by assumption they have unique factorisations and so the two factorisations cannot be different.
You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and G[font="sans-serif"]ö[/font]delization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.
for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as
I've not heard of [color="#1C2837"]G[font="arial, sans-serif"]ö[/font]delization, but that just looks to be the prime factorisation of an integer for which it is quite easy to prove that a) it exists, and b) that it is unique.
[color="#1C2837"]
[color="#1C2837"]An intuitive proof for existance would be:
let N be a number, either N is prime or it is not prime.
If it is not prime then there must exist a prime P and a possibly non-prime M (otherwise N would be prime).
[color="#1C2837"]In the same way, repeat with M instead, and eventually you either get a prime number, or 1.
from which it is easy to construct a formal inductive proof.
[color="#1C2837"]
[color="#1C2837"]Proof of uniqueness is a little bit harder, a sketch proof would be:
Let N be the smallest integer expressible as the product of two minimal; non-identical sets of primes s1,s2..sn q1,q1...qm
[color="#1C2837"]as N is the smallest such number, then s1, and s2...sn, must have unique factorisations as they are smaller than N.
[color="#1C2837"]p1 then, must either divide s1, or s2...sn (or both, not important) and as all are prime, si = qj for some i,j. By removing si,qj from the two non-equal factorisations we get two smaller, equal numbers. as they are smaller than N, by assumption they have unique factorisations and so the two factorisations cannot be different.
You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and G[font="sans-serif"]ö[/font]delization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.
for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as
2^1 * 3^4 * 5^9 * 7^16 = 10515106938037816406250
Thanks both of you I understand perfectly now, big numbers though! I think I was just a little put off by all that complex-looking formula.
