Reverse Engineering in Number Theory

Sometimes you know that a formula has a connection to a given information, but you don't know what exactly the connection is. In such cases you have to reverse engineere the formula yourself.

You have a natural number n > 1 n>1 where

n = p 1 e 1 p 2 e 2 p 3 e 3 n={ p }_{ 1 }^{ { e }_{ 1 } }\cdot { p }_{ 2 }^{ { e }_{ 2 } }\cdot { p }_{ 3 }^{ { e }_{ 3 } }\cdot \dots

is the prime factorisation of n n ( p i { p }_{ i } is the i i -th prime number; e i { e }_{ i } is a non negative integer). You know that the folowing expression has something to do with n n . But what?

i = 1 ( 1 p i e i + 1 1 p i ) \prod _{ i=1 }^{ \infty }{ \left( \frac { 1-{ { p }_{ i } }^{ { e }_{ i }+1 } }{ 1-{ p }_{ i } } \right) }

Try it like you don't know the possible answers.

It is the product of all non coprime integers, which are less then n n . It is the sum of all divisors of n n . It is the sum of all non coprime integers, which are less than n n . It is the product of all divisors of n n .

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

CodeCrafter 1
Oct 13, 2019

First you can notice that the expression inside the product is the explicit form for a geometric sum. Therefore we can manipulate the expression a bit:

i = 1 ( 1 p i e i + 1 1 p i ) = i = 1 ( j = 0 e i p i j ) \prod _{ i=1 }^{ \infty }{ \left( \frac { 1-{ { p }_{ i } }^{ { e }_{ i }+1 } }{ 1-{ p }_{ i } } \right) } =\prod _{ i=1 }^{ \infty }{ \left( \sum _{ j=0 }^{ { e }_{ i } }{ { { p }_{ i } }^{ j } } \right) }

An important fact is, that most e i e_i 's are 0 0 . Therefore in the infinite product many of the p i e i {p_i}^{e_i} parts will be 1 1 and we can ignore them.

Then you could try an example for n n (because we are reverse engineering). An Example with only one prime factor: 9 9

i = 1 ( j = 0 e i p i j ) = j = 0 2 3 j = 3 0 + 3 1 + 3 2 \prod _{ i=1 }^{ \infty }{ \left( \sum _{ j=0 }^{ { e }_{ i } }{ { p_i }^{ j } } \right) } =\sum _{ j=0 }^{ 2 }{ { 3 }^{ j } } ={ 3 }^{ 0 }+{ 3 }^{ 1 }+{ 3 }^{ 2 }

Now you could try an example with two prime factors: 36 36

i = 1 ( j = 0 e i p i j ) = ( j = 0 2 2 j ) ( j = 0 2 3 j ) = ( 2 0 + 2 1 + 2 2 ) ( 3 0 + 3 1 + 3 2 ) \prod _{ i=1 }^{ \infty }{ \left( \sum _{ j=0 }^{ { e }_{ i } }{ { p_i }^{ j } } \right) } =\left( \sum _{ j=0 }^{ 2 }{ { 2 }^{ j } } \right) \cdot \left( \sum _{ j=0 }^{ 2 }{ { 3 }^{ j } } \right) =\left( { 2 }^{ 0 }+{ 2 }^{ 1 }+{ 2 }^{ 2 } \right) \cdot \left( { 3 }^{ 0 }+{ 3 }^{ 1 }+{ 3 }^{ 2 } \right)

If we factor out this product we get some messy stuff. But by rearanging in a grid we get something familiar :

2 0 2^0 2 1 2^1 2 2 2^2
3 0 3^0 1 2 4
3 1 3^1 3 6 12

|| 3 2 3^2 || 9 || 18 || 36 ||

And now we have all the divisors of n n arranged in a grid (2D-plane). If we would take a number n n with 3 prime factors we could rearange these summands in a 3D-space; 4 prime factors in a 4D-space and so on. And we always get the sum of all divisors of our choosen number n n .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...