Puzzle about odd semi-primes and Euler totient

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Thu Aug 04, 2016 6:19 pm UTC

Hi,

I will start by an example :

n=21
n is an odd semi-prime = 3*7 (3 and 7 are distinct prime)
The biggest power of 2 immedialy < 21 is = 4
So 2^4=16<21

Let us compute 21 mod (2^k) with k varying from 2 to 4

21=1 mod 2
21=1 mod 4
21=5 mod 8
21=2 mod 16

If we sum the residue modulo : 1+1+5+5=12 (1)

The Euler totient of phi(21)=(3-1)*(7-1)=2*6=12 (2)

So the is an equality between (1) and (2)

n=91=7*13 has that property too

How many odd semi-primes have such properties?
Is the set of those semi-primes infinite?
Can we find quickly such numbers by using a closed formula?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Fri Aug 05, 2016 1:53 pm UTC

Without filtering the odd semi-primes I have obtained this list up to 500 :

6,10,12,18,20,21,24,27,36,40,48,72,75,80,91,96,98,119,138,144,160,192,196,276,288,320,377,384,392,485

So 30 numbers (let us call them Eulerian composite numbers) out of 500 (6%).
Only 5 are odd semiprimes : 21,91,119,377,485

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Fri Aug 05, 2016 4:02 pm UTC

If we write in base 2 the number n=pq (where p and q are odd distinct prime) it will be easier to find a way to know if any number n is Eulerian odd semi prime number.
Assuming that we could recognize quickly an Eulerian odd semi prime number it will lead to an easy factorization of n.
I know that only very few semi prime numbers will fall in my case. Theoretically it will be a good result.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Fri Aug 05, 2016 6:00 pm UTC

I computed n up to 10000. If I did not make a programming mistake I obtained only 67 Eulerian composite numbers.
What is strange is that after the Eulerian odd number 1323 which is not semi prime there was only even numbers.
Why? I do not know for now.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Fri Aug 05, 2016 6:39 pm UTC

I hope there was no mistake. Here are the 67 Eulerian composite numbers for n up to 10000:

6,10,12,18,20,21,24,27,36,40,48,72,75,80,91,96,98,119,138,144,160,192,196,276,288,320,377,384,392,485,546,552,576,640,768,784,802,1092,1104,1152,1251,1280,1323,1536,1568,1604,2184,2208,2304,2560,2602,3072,3136,3154,3208,4368,4416,4608,5120,5204,6144,6272,6308,6416,8736,8832,
9216

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Sun Aug 07, 2016 11:21 am UTC

Goahead52 wrote:I hope there was no mistake. Here are the 67 Eulerian composite numbers for n up to 10000:

6,10,12,18,20,21,24,27,36,40,48,72,75,80,91,96,98,119,138,144,160,192,196,276,288,320,377,384,392,485,546,552,576,640,768,784,802,1092,1104,1152,1251,1280,1323,1536,1568,1604,2184,2208,2304,2560,2602,3072,3136,3154,3208,4368,4416,4608,5120,5204,6144,6272,6308,6416,8736,8832,
9216

Hi,

I discovered a pattern in this sequence :
For example 6,10,18 are "roots"
All 6*2^k with k=1 to the infinite are Eulerian composite numbers (ECN) : 12,24,48,
10 is a root :
20,40,80,160,320,.....
18,36,72,144,....
6,10,18 are even
Is there a pattern for odd numbers?

So if we found the "roots" it will be easy to generate the following and prove that those numbers are infinite.
I have no explanation now for why this happen.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Sun Aug 07, 2016 12:27 pm UTC

I do not have enough odd numbers to see if there is a pattern :
Only 9 Eulerian composite numbers (ECN) :

21,27,75,91,119,377,485,1251,1323

I need to compute n up to 1000000 to have more.
On Excel it is going to take lot of time.
If I discover some pattern for odd numbers it will be then easy to compute the Euler totient for huge odd numbers.
Maybe there is a window to set "new" theorems.
I need your help! and your thoughts!
Thank you.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Sun Aug 07, 2016 4:47 pm UTC

For n to up 100000 I obtained 100 ECN :

6,10,12,18,20,21,24,27,36,40,48,72,75,80,91,96,98,119,138,144,160,192,196,276,288,320,377,384,392,485,546,552,576,640,768,784,802,1092,1104,1152,1251,1280,1323,1536,1568,1604,2184,2208,2304,2560,2602,3072,3136,3154,3208,4368,4416,4608,5120,5204,6144,6272,6308,6416,8736,8832,9216,10240,10408,12288,12544,12616,12832,17472,17664,18432,19911,20480,20816,24576,25088,25232,25664,26391,34944,35328,36864,40960,41632,49152,50176,50464,51328,69888,70656,73728,81920,83264,85557,98304

I have only three more odd numbers :
19911,26391,85557

Only one is semi prime 19911=3*6637
I have found some patterns for some odd numbers like 91.
91*12=1092
1092 as root will make all the numbers = 1092*2^k Eulerian composite numbers (ECN)
91 and 12 are both ECN.
So are there other ECN product of 2 ECN?
I do not not know for now.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Puzzle about odd semi-primes and Euler totient

Postby Goahead52 » Sun Aug 07, 2016 9:06 pm UTC

Here is another strange :
Let us call S(n) the sum of modulo power 2 up to the biggest power < n
Let us call phi(n) the Euler totient of n

If we sum all the S(n) and all the phi(n) up to 100000 we obtain almost a similar sum :


Sum of the S(n)`s = 3107218357
Sum of the phi(n)`s = 3039610754
Ratio sigma S(n)/sigma phi(n) =1.022242191

If the ratio goes to 1 when n goes to infinity then we could use S(n)`s which is not hard to compute instead of using phi(n)`s. S(n) does not need the n`s to be factorized and more than that. I plotted the S(n)`s and it seems that we could reach a closed formula for the sum of S(n)`s. It requires some calculations to find it but it is doable.
As I can not compute for n too large I can not know if such equality occur. I did it for n up to 100000 using Excel.
But if someone could give more precise result (n as large as possible) then we have to find why?
If we can prove that the limit converges to 1 then we could use it as theorem to reach many results.
Thank you for any clue.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: Gwydion and 7 guests