23.2.17

Generating Powers of 2 Again

While looking into proving the algorithm I described here, I stumbled upon yet another algorithm for generating powers of 2.

This new algorithm is based on the following recurrence relation:

a1 = (n+1)/2        given an odd n  
ai = ai-1/2              if ai-1 is even
ai = (ai-1-1)/2 + a1 if ai-1 is odd

I claim that the recurrence relation above generates all powers of (n+1)/2 mod n in consecutive order and all powers of 2 mod n in reverse order.

This follows from the first part of the algorithm that I previously described, namely the claim below:

Claim: Given an odd integer n and k = (n+1)/2, then all consecutive multiples of k mod n, namely 1*k mod n, 2*k mod n, 3*k mod n,..., (n-2)*k, (n-1)*k, are equal to k, 1,  k + 1, 2,  k + 2,  3, k + 3, .... , n-1,  k - 1 respectively.

Proof:
Since n is an odd integer then Zn is a commutative ring closed under multiplication and addition with an identity element and so the following algebraic expressions hold.

Since k = (n+1)/2, then 2*k mod n = 2(n+1)/2 mod n = n+1 mod n and since n mod n = 0 then
2*k mod n = 1 mod n.

Similarly for all even multiples x of k: x*k = x/2.

On the other hand, 3*k mod n = ((n+1)/2  + (n+1)/2  + (n+1)/2) mod n
                                                 = (2(n+1)/2 + (n+1)/2) mod n
                                                 = 2(n+1)/2 mod n + (n+1)/2 mod n
                                                 = 1 mod n + (n+1)/2 mod n
                                                 = (1 +  (n+1)/2) mod n.

Similarly, for all odd multiples y of k: y*k = (n+1)/2 + (y - 1)/2
.'.

The index of each term in the sequence k, 1,  k + 1, 2,  k + 2,  3, k + 3, .... , n-1,  k - 1 , which is essentially the ((n+1)/2)th row of the multiplication table of Zn, reveals a few ways of finding powers of 2 mod n.

My previous algorithm for generating consecutive powers of 2 mod n in reverse order required the explicit generation of this particular row but the recurrence relation for the new algorithm that I described in the beginning of this post does not.

I implemented the new algorithm in Javascript below for reference.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 and (n+1)/2 mod n 
 ---------------------------------------------------- */  
//generate powers of 2 from highest to lowest exponent
function powers_of_two_backwards_again(n)
{
 var k = (n+1)/2;
 var halfie = k;
 var powers = new Array();
 do{
    powers.push(k); 
    if (k%2 == 0)
    {k = k/2;}
    else
    {k = ((k-1)/2)+halfie;}
   }while(k != 1)
 return powers;
}

And embedded bellow is a demo.



This algorithm is reminiscent of the algorithm behind the Collatz conjecture.

15.2.17

I Can Do Proofs

In my last entry I made a typo when describing a sequence using two different formulas.

The first formula is 2i + (2i-1 - 3) if i is even or 2i + (2i-1 + 3) if i is odd for all i > 2
The second formula is 3*(2i-1 - 1) if i is even or 3*(2i-1 + 1) if i is odd for all i > 2

I claim that these two formulas are equivalent.

It may look counterintuitive that if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and that if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1) but I can actually prove it.

Below I provide a proof using mathematical induction to show off my mad skillz.

Claim: For all i > 2, if i is even then 2i + (2i-1 - 3) = 3*(2i-1 - 1) and if i is odd then 2i + (2i-1 + 3) = 3*(2i-1 + 1).

Proof by weak mathematical induction:

Base Case: i = 3

 23 + (23-1 + 3) = 8 + (4 + 3) = 15
 3*(23-1 + 1) = 3*(4+1) = 15            Clearly, base case holds

Inductive Step:

Suppose that 2i + (2i-1 + 3) = 3*(2i-1 + 1) is true for an odd i, must show that the claim is also true for the next odd i, namely i + 2.

Since 2i + (2i-1 + 3) = 3*(2i-1 + 1) then 2i  3*(2i-1 + 1) - (2i-1 + 3) 

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 +  1) - ( 2i + 2 - 1 + 3)
2i + 2 = 3*2i+1  + 3 -  2i+1  - 3
2i + 2 = 3*2i+1  + 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2

Similarly, suppose that 2i + (2i-1 - 3) = 3*(2i-1 - 1) is true for an even i, must show that the claim is also true for the next even i, namely i + 2

Replacing i with i+2 yields

2i + 2 = 3*(2i +2 - 1 -  1) - ( 2i + 2 - 1 - 3)
2i + 2 = 3*2i+1  - 3 -  2i+1  + 3                  
2i + 2 = 3*2i+1  - 0 -  2i+1
2i + 2 = 2*2i+1   = 2i + 2
.'.



11.2.17

A Shrewd Sequence

In previous entries I categorized integers n between 2i and 2i+1 where the order of 2 mod n has a common formula for each i.

For example:
1. I proved that if n is a Mersenne number (an integer of the form 2i - 1), then the order of 2 mod n is equal to i.

2. Then I conjectured that if n is of the form 2+ 1 then the order of 2 mod n is equal to 2*i.

3. I also conjectured that if n is of the form:

2i + (2(i-1) - 3) if i is even 
or 2i + (2i-1 + 3) if i is odd


or in other words of the form (here's the proof that these two formulas are equal)

3*(2i-1 - 1) if i is even
3*(2i-1 + 1) if i is odd 

then the order of 2 mod n is i + (i - 2)


Another example that I have not previously published on this blog is also based on just a conjecture that may turn out to be false.

Conjecture: For each i > 3 there exists at least one integer n such that 2< n < 2i+1 and the order of 2 mod n is equal to (i-1)*(i-2)

Below is a sequence generated using the first occurrence of such integers between 2i and 2i+1 for each i > 3

21, 35, 75, 231, 301, 731, 1241, 2079, 7513, 8337, 16485, 39173, 66591, 131241, 371365, 539973, 1125441, 2153525,...


Below is a slow calculator for finding the order of 2 mod n for any odd integer n:

19.1.17

Wiener Werkstaette Kunstlerinnen

Another city I visited in 2016 with the intention of checking out a modern art exhibit was Vienna, Austria.



I went to see "Das bessere Haelfte: Judische Kunstlerinen bis 1938", which celebrates the contribution of Jewish women to the development of Viennese modernism.



The exhibit blends together the works of well established Viennese artists with the works of the unfairly forgotten ones.



Contrary to popular belief at the time, these artists came from different backgrounds, and were not just "daughters of high dignitaries or products of wealthy households" as Adolf Loos called the women of Wiener Werkstaette in 1927.



One of the artist featured in the exhibit is Friedl Dicker, who was born in Vienna in 1898 into a poor Jewish family. In 1915 Dicker joined the textile department of the School of Art and Crafts in Vienna.  
In 1919 she went to Weimar Bauhaus to study. She returned to Vienna four years later where she established a furniture atelier, which received awards at several exhibitions.

The photo below depicts a reproduction based on a collage by Friedl Dicker entitled "The Bourgeoisie Becomes Fascist" originally made in 1932.




Everyone can be an artist but not every artist can be a visionary. Friedl Dicker was a visionary.

In the above piece she managed to capture the spirit of the problem, which 10 years later nearly destroyed Europe, like no other artist before or after her.

Modern art played a central role in World War II. The Nazis felt threatened by it to such an extent that they organized a propaganda exhibit where popular modernist works were derided. Psychologists such as Carl Jung,  who enjoyed a blossoming career during the Nazi regime, and whose pseudo-scientific ramblings still corrode the popular Western culture today, saw modern art as a symbol of "corrosive character".  According to letters written by Jung during the Nazi regime in Germany, he was a Nazi sympathizer, yet he denied being a Nazi sympathizer after Nazi Germany lost WWII.

Meanwhile, Friedl Dicker had the option to flee Nazi Europe shortly before she was sent to a concentration camp but she chose to stay with those who couldn't go anywhere and tried to lift their spirits with art workshops where they drew flowers and landscapes to escape their gruesome reality. In 1944 she was gassed in Auschwitz along with some of her students.

3.1.17

Multiple Positions

Previously, I generated a sequence using the following recurrence relation and I made a few conjectures about it.

2i + (2(i-1) - 3) if i is even 
or 2i + (2i-1 + 3) if i is odd

I also wrote an algorithm based on this recurrence relation to generate the first few such integers up to some limit. The first 20 terms of the sequence with initial term i = 3 are:


Obviously, each term in this sequence is divisible by 1 or more primes.

Claim: If a term in this sequence at position b is divisible by a prime p then the term at position
b + (p-1)  is divisible by p.

This claim holds for all other recurrence relations of the form

2i + (2(i-1) - k) if i is even 
or 2i + (2i-1 + k) if i is odd

where k is any odd integer


It is easy to see it because it is a result of the fundamental theorem of algebra in that every integer can be represented as a product of primes.

For example, the first 20 terms of the sequence generated with the recurrence relation

2i + (2(i-1) - 7) if i is even 
or 2i + (2i-1 + 7) if i is odd

are:



The first term 17 is a prime at position 0, and the term at position 0 + (17 - 1) = 16 is divisible by 17.
In fact 1572857/17 = 92521.

Similarly, 55 = 11* 5 is at position 1, so the term in the sequence at position 1 + (11 - 1) = 11 is divisible by 11 and the term at 1 + (5 - 1) = 5 is divisible by 5.

I'm willing to bet that the 90th term in the sequence is divisible by 89 and the 201st term is divisible by 199.

377 = 13*29 is at position 4 in the sequence and the term in the sequence that's at position 4+(13-1) = 16 is 1572857, which is divisible by 13. In fact, the term at position 4+(29-1) = 32 is 103079215097 and it is divisible by 29 among other integers.

And so on.

One of the claims I made for the sequence where k = 3 is that every single element in it is divisible by 3. It is also easy to see why this is so using the claim above since the first 2 terms of the sequence at position 0 and 1 respectively are divisible by 3. Namely, if the initial i = 3 then clearly the first term of the sequence at position 0 is 23 + (22 - 3) = 15, which is divisible by 3 so the term at position 0+(3-1) = 2 will also be divisible by 3. Therefore, every second term will be divisible by 3. To calculate the term at position 1, I plug in i = 4 so 24+ (23 - 3) = 21, which is also divisible by 3 so every third element of the sequence will also be divisible by 3. 

Similarly, if k is equal to any other odd multiple of 3, then the sequence generated using the relation


2i + (2(i-1) - k) if i is even 
or 2i + (2i-1 + k) if i is odd

is composed of terms such that every term is divisible by 3.

I also made another claim related to the sequence when k = 3. I claimed that for each term n where

n = 2i + (2(i-1) - 3) if i is even 
or n = 2i + (2i-1 + 3) if i is odd

the order of 2 mod n is i+(i-2) 


I haven't been able to see why this is the case yet but it holds for the first 50 terms of the sequence, and beyond as far as I can see.

Below is a graphic I made of different sequences generated for different k with initial i = 4.


The interesting thing about this is that only the sequence for k = 1 exists in the OEIS.org database of sequences but it is generated using a different relation, and the sequence itself is an amalgamation of sequences concerning powers of 3.

Neither of the other sequences I presented here have found their way into the OEIS.org database of integer sequences.

31.12.16

2016 Sequences

I came up with 7 different sequences in 2016 and I thought I'd put them all in one place as some of them are slightly related to one another.

1. The first sequence is the sequence generated by powers of 2 mod n when n is the product of 2 distinct safe primes. The sequence was published in the OEIS.org with sequence number is A269453. Here are the first few terms of the sequence:

12, 20, 30, 44, 33, 92, 110, 116, 69, 174, 164, 230, 212, 246, 290, 318, 332, 356, 410, 253, 452, 249, 530, 534, 524, 638, 678, 692, 716, 830, 393, 902, 764, 890, 932, 956, 1038, 1166, 1130, 537, 1004, 573, 1334, 1124, 1310, 1172, 1398, 717, 753, 1436, 1730, 913, 1886, 1686, 1790

2. Then came the the sequence of the products of two distinct safe primes, which is now published in the OEIS.org under sequence number A269452

24, 40, 60, 88, 132, 184, 220, 232, 276, 348, 328, 460, 424, 492, 580, 636, 664, 712, 820, 1012, 904, 996, 1060, 1068, 1048, 1276, 1356, 1384, 1432, 1660, 1572, 1804, 1528, 1780, 1864, 1912, 2076, 2332, 2260, 2148, 2008, 2292, 2668, 2248, 2620, 2344, 2796, 2868, 3012, 2872, 3460, 3652, 3772, 3372


3. Looking at these 2 sequences made me discover a third sequence, which I dedicated to my great grandmother Yona because at the time I thought it was the most important result I'd come up with. This sequence consists of safe primes not congruent to -1 mod 8 and it is now published with a sequence number A269454.

5, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907, 2027, 2099, 2459, 2579, 2819, 2963, 3203, 3467, 3779, 3803, 3947, 4139, 4259, 4283, 4547, 4787, 5099, 5387, 5483, 5507, 5939, 6659, 6779, 6827, 6899, 7187, 7523


The next 3 sequences I came up with involve the Collatz conjecture, which is an open problem in Mathematics. 2 of these sequence were published and the last one was denied and so it remains unpublished because it seemed "artificial"

4. The first sequence of the Collatz trio is the sequence of Collatz primes(A276260), and it only has 9 terms. If a 10th term exists, it would have to be really really large.

5, 13, 17, 53, 61, 107, 251, 283, 1367

5. The second sequence is the sequence of Collatz products, and it has many more terms. It is published under the sequence number A276290 .

25, 35, 55, 65, 77, 85, 95, 115, 133, 143, 145, 155, 161, 185, 203, 205, 209, 215, 217, 235, 253, 259, 265, 287, 295, 305, 329, 341, 355, 365, 371, 391, 395, 403, 407, 415, 427, 437, 445


6. The third sequence of the Collatz trio was never published and here I explain it in some detail.  The first few terms are:

5,27,21,107,85,427,341,1707,1365,6827, 5461

7. The last sequence that I came up with in 2016 is the sequence I described here. I haven't attempted to publish this sequence anywhere yet. The first few terms are:

15, 21, 51, 93, 195, 381, 771, 1533, 3075, 6141

2016 has been the year of discovery for me. I discovered many different results, some of which I even managed to prove. Also in 2016 I learned not to be intimidated by sharing my results with the public.

30.12.16

Just another sequence

In my previous post I talked about the order of 2 mod n where n is an integer such that either n = 2^i + (2^(i-1) - 3) when i is even or n = 2^i + (2^(i-1) + 3) when i is odd.

I conjectured that the order of 2 mod n for such n is i + (i - 2) regardless of whether i is even or odd.

The recurrence relation for generating all such n up to a limit is :

2i + (2(i-1) - 3) if i is even
or 2i + (2i-1 + 3) if i is odd

For the fun of it, I wrote a simple script to generate the first few such integers up to some limit.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate the 3sequence  
  
 ---------------------------------------------------- */  
function gen_seq(i, limit, a)
{
 var j = i - 1;
 var n = Math.pow(2,j);
 var m = Math.pow(2,i);
 if (i < limit)
 {
  if (i % 2 != 0)
  {
   n = n + 3;
  }
  else
  {
   n = n - 3;
  }
  a.push(m+n);
  i = i + 1;
  gen_seq(i, limit, a)  
 }
 return a;
}

Here's the output for limit = 12:

15, 21, 51, 93, 195, 381, 771, 1533, 3075, 6141

Obviously, there is another way to generate this sequence than the one I use in my script. Each term in the sequence can also be generated by multiplying 3 and 2^i - 1 if i is odd or 3 and 2^i + 1 if i is even.

3*5 = 15 where 5 = 2^2 + 1
3*7 = 21 where 7 = 2^3 - 1
3*17 = 51 where 17 = 2^4 + 1
3*31 = 93 where 31 = 2^5 - 1

and so on.

28.12.16

Between 2 i's

Previously I talked about the order of 2 mod n when n is either equal to 2^i + 1 or 2^i - 1

How about the order of 2 mod n for other integers n, which are between 2^i and 2^(i+1)?

21.12.16

The circle of i

Every day many people around the world look for the next largest Mersenne prime. A Mersenne prime is a Mersenne number that's also prime.

A Mersenne number is an integer of the form 2^i - 1 where i must also be prime but this condition is not strongly enforced in all texts and certainly not on this blog.

I prefer the loose definition where i is not necessarily a prime. With this loose definition in mind, the first few Mersenne numbers are:

0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, ...

The first few Mersenne prime numbers are:

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ...

In a previous post I proved that the order of 2 mod n is equal to i where n is a Mersenne number of the form 2^i - 1

For example, the order of 2 mod 15 is 4 and 15 = 2^4 - 1.

A Mersenne number can also be a product of 2 or more distinct primes.

The first few products of 2 distinct primes that create a Mersenne number are:

5*3 = 15, 7*73 = 511, 23*89 = 2047, 47*178481 = 8388607


At the other end of the spectrum of Mersenne numbers are integers of the form 2^i + 1.

They don't have a fancy name but some of them do show up in fancy parts of Number Theory. I'll call them MersenneSofit numbers.

The first few such numbers are:

2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, ...

The only prime MersenneSofit numbers that I was able to find are also Fermat primes even though the set of MersenneSofit numbers is not equivalent to the set of Fermat numbers. I find this quite fascinating although it is possible I missed a prime in my savage late night calculations.

Here are the only MersenneSofit primes I could find so far:

3, 5, 17, 257, 65537

As I already said, these are also the only Fermat primes currently known.

Regardless of whether prime or composite, I claim that the order of 2 mod n for all n of the form 2^i + 1 is 2*i.

A Mersenne Sofit number can also be a product of distinct primes. The first few products of 2 distinct primes are:

5*13 = 65
3*43 = 129
17*241 = 4097
3*2731 = 8193
3*43691 = 131073
3*174763 = 524289
17*61681 = 1048577
3*2796203 = 8388607
17*15790321 = 268435457

Note: although there are more Mersenne primes than MersenneSofit primes, there seem to be less products of 2 distinct primes that form Mersenne numbers than there are products of 2 distinct primes that form MersenneSofit numbers.

4.12.16

Salvador Dali

Merriam-Webster defined 2016 as the year of the surreal. As a big fan of surrealism, I decided to visit  the birth place of Salvador Dali where he built a museum to display some of his work.


Salvador Dali Museum in Figueres, Spain



The museum from the inside
Salvador Dali built this museum after his muse and life partner Gala, born as Elena Ivanovna Diakonova, died.   



He added her name to many of his works to illustrate the influence she had on him. He was not the only artist she influenced but he was okay with that.


Salvador Dali museum

Dali also dabbled with making sculptures and jewellery, and there's a separate jewellery museum within the same museum building in Figueres, which is not pictured here.



A part of Gala exists in all of Dali's famous works, either in the form of her face or her name, or some other form. 

Their marriage was unconventional. He had to ask for a written permission to visit her. She often had gang bangs that Dali knew about and he was happy for her. 


A ceiling mural at the museum

The museum contains many of Dali's earlier, less famous works painted in a time when he clearly struggled to find his own style.