Problems & Puzzles: Puzzles

Puzzle 1032. Integers EOM Vicente Felipe Izquierdo sent the following nice puzzle: Here are some observations about the prime factors of a number, calculating which are prime of even or odd index.   Let us calculate for each number k its prime factors: -If All its prime factors are of Even index, we will assign a "E". -If All its prime factors are of Odd index, we will assign an "O". -In another case, a Mixture of prime factors of even and odd index, we will assign an "M".   With this rules, the first 100 integers numbers can be represented as: "EOEOOMEOEOOMEMMOOMEOEOOMOMEMEMOOMOMMEMEOOMEOMOOMEOMMEMOMEMO MEOEOMMOOMMEMOMMMMMEOEOOMOMEOEMEOMOMMOMMO"   Among other things, we can observe the following: -Repeats of string "OO" occur, but NOT of string "EE". -There are no 3 or more consecutive "O's". -The list of the first elements of each "OO" pair is: {4, 10, 16, 22, 31, 40, 46, 67, 82, 109, 124, 127, 136, 166, 187, ...} and the difference between each term is a multiple of 3. Some questions: 1-It is possible to get the sequence "EE"?. If NOT, why? 2-It is possible to obtain sequences of more than 2 "OO"? If NOT why? 3-Why is the distance between every 2 sequences "OO" a multiple of 3, or you can find any distance other than a multiple of 3? Later he added:   Another interesting observation about the representation of integers according to their prime factors.   - For every integer n of type "O", the parity of the prime factors of their multiples (k n, for k-> 1..inf) generate the same sequence, for example multiples of 2 generate: {"OOMOOMMOMOOMMMMOOMMOMOOMOMMMMMOOMOMMMMMOOMMOMOOMMO ..."} multiples of 5 generate: {"OOMOOMMOMOOMMMMOOMMOMOOMOMMMMMOOMOMMMMMOOMMOMOOMMO ..."}   - For every integer n of type "E", the parity of the prime factors of their multiples (k n, for k-> 1..inf) generate the same sequence, for example multiples of 3 generate: {"EMEMMMEMEMMMEMMMMMEMEMMMMMEMEMMMMMMMEMEMMMEMMMMMEM ..."} multiples of 7 generate: {"EMEMMMEMEMMMEMMMMMEMEMMMMMEMEMMMMMMMEMEMMMEMMMMMEM ..."}   - For every integer n of type "M", the parity of the prime factors of their multiples (k n, for k-> 1..inf) generate the same sequence, for example multiples of 6 generate: {"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM ..."} multiples of 7 generate: {"MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM ..."}   Which suggests to me that in the integers there is a certain fractal structure, imposed by prime numbers, according to the criterion of the type of parity of its prime factors., but I can be wrong !!! Q. Can you provide an explanation for the Izquierdo's observations & questions?

---

During the week from March 27 to April 2, 2021, contributions came from Emmanuel Vantieghem, Adam Stinchcombe, Giorgos Kalogeropoulos and Oscar Volpatti

***

Emmanuel wrote:

1) Take two consecutive numbers.  At least one of them is divisible by  2  which is a prime on index  1  and hence cannot have the assignment  E.  Thus,  EE is impossible.

2) Take three consecutive numbers.  At least one of them is divisible by  3  which is a prime of even index.  Thus, OOO  is impossible.
3) If two consecutive numbers both have the assignment O  no one of them can be divisible by  3.  Hence, the first of the two numbers must be  3m +1  (and the second is  3m + 2).
The other observations all are consequences of the rule that the prime factors of a number  n  are also prime factors of a multiple  k*n.

 

***

Adam wrote:

Given the definition: enumerate the primes p=p(n) in order and say p has the parity of n.  Then we can explain all the patterns seen:


No EE.  One of two consecutive numbers is even, so has a factor of 2, with the parity of 2, the first prime, being odd.  In two consecutive numbers, there is always a number which is either O or M.


No OOO.  In three consecutive numbers there is always a multiple of 3=E and so at least one of three consecutive numbers is of type E or M.


The first part of an OO pair is 1 mod 3.  If the first O in an OO pair is 3n+0 then it is either E or M (having the factor 3=E).   If the first O in an OO pair is 3n+2 then the second O is 3n+2+1 = 3(n+1) and is either E or M (having the factor 3=E).  So an OO pair starts with a number of form 3n+1 and all first terms differ by a multiple of 3.  {  (3n+1) - (3m+1) = 3(n-m). }


The sequence of multiples of n becomes clear when you think about why multiples of n of type M are all of type M.  Basically, more factors --- n*k --- can not destroy the mixed nature of n.  Suppose n is of type M and is divisible by a p = p(2n) of type E and also divisible by a prime q = p(2m+1) of type O, then n*k has both the E factor p and the O factor q: n*k = p*q *(k*n/(pq)) where n/(pq) is an integer.  All multiples of n are of type M.


If the type of factors x and y are known, then the type of x*y follows the rules: (E and E) is E, (E and O) is M, (E and M) is M, (O and O) is O, (O and M) is M, (M and M) is M, and it is commutative (R and S) is (S and R).  So the sequence of multipliers k (ignoring k=1) ---  OEOOMEOEOOMEMM...--- is just joined to the type of n:


(1) (ignoring the first multiple n*1) if n is of type E, then multiples of n are of type (E and O)(E and E)(E and O)(E and O)(E and M)... = MEMMM....

 (2) (ignoring the first multiple n*1)  if n is of type O, then multiples of n are of type (O and O)(O and E)(O and O)(O and O)(O and M)... = OMOOM...

***

Giorgos wrote:

Q1. It is not possible to get "EE":

       If we take two consecutive numbers one of them must be odd and the other must be even. 

       The even number has 2 as a prime factor (with index 1) which means that the even number can only be "O" or "M" and never "E"

 

Q2. You cannot get more than 2 "OO" 

       If we take 3 consecutive numbers one of them must be divisible by 3.

       This means that one of them has 3 as a prime factor (with index 2) and can only be "E" or "M" and never "O"    

 

Q3. If we use the fact from Q2 we can see that the sequence "OO" can only appear in the place {x,y} where x=1mod3 and y=2mod3.

       So, all the members x of the list must be congruent to 1mod3. This is why their distance will always be a multiple of 3

 

***

Oscar wrote:

All Izquierdo's observations about his EOM-representation function f(k) can be rigorously proven.

 

About sequence f(k); representations of consecutive integers.

 

The odd-index prime 2 divides all numbers of the form k = 2*t, so their representation must be "O" or "M".

Hence, there can be no blocks of two consecutive "E"s; there can be isolated "E"s, all at positions of the form k = 2*t+1.

 

The even-index prime 3 divides all numbers of the form k = 3*t, so their representation must be "E" or "M".

Hence, there can be no blocks of three consecutive "O"s; there can be blocks of two consecutive "O"s, all starting at positions of the form k = 3*t+1, so that the distance between two such starting points is always a multiple of 3.

 

About sequences f(n*k); representations of multiples of n, with n>1.

 

The EOM-representation function f(k) has an interesting property.

If we know the representations of two integers a>1 and b>1, then we can find the representation of their product a*b according to the following composition rules:

"O" x "O" = "O"

"E" x "E" = "E"

"M" x "M" = "M"

"O" x "E" = "E" x "O" = "M"

"O" x "M" = "M" x "O" = "M"

"E" x "M" = "M" x "E" = "M"

 

If we apply the composition property  f(a*b) = f(a) x f(b), we can rewrite the sequence f(n*k) as follows:

f(n), f(n) x f(2), f(n) x f(3), f(n) x f(4), ...

Therefore, two integers n1 and n2 sharing the same representation always generate the same sequence, as conjectured by Izquierdo.
 

Integers EOMN

 

What about the integer 1, which has no prime factors at all?

Izquierdo assigned to 1 the value "E", but it's better to reserve for this case a special value like "N", obtaining a EOMN-representation function which satisfies the following additional composition rules:

"N" x "N" = "N"

"O" x "N" = "N" x "O" = "O"

"E" x "N" = "N" x "E" = "E"

"M" x "N" = "N" x "M" = "M"

 

In this way, the composition property  f(a*b) = f(a) x f(b) holds for every pair of positive integers.

By further defining f(0) = "M" and f(-k) = f(k), the composition property also holds for every pair of integers, without restrictions.

***