2.6.17

The Graphing Calculator

When I first moved to Canada I was simultaneously shocked and pleasantly relieved to find out that calculators are mandatory in high schools.

26.4.17

Subsets of Safe Primes

The set of safe primes is composed of 2 mutually disjoint sets: the set of tough primes and the set of steady primes.

 a list of the first few safe primes with tough primes in light blue background; the rest are steady primes

The main difference between these two sets lies in the structure of the exponentiation tables of their elements. For a tough prime p, I conjecture that:

Conjecture: If p is a prime of the form 8n+7, then the order of even powers of 2 mod p is p-1 and the order of odd powers of 2 mod p is (p-1)/2

In contrast, for a steady prime q I conjecture that:

Conjecture: If q is of the form 8n-1 such that 4n-1 and 8n-1 are also primes, then the order of all powers of 2 mod q is equal to (p-1)/2

Example: Let p = 11 and let q  = 7. Below are the corresponding exponentiation tables of Z11 and Z7.
The order of 2 mod 11 = 10, which is equal to the order of 8 mod 11, but the order of 4 mod 11 is half of that. Whereas in  Z7 the order of all powers of 2 is equal to 3.

Steady primes are the only primes where the order of all powers of 2 mod p is the same.  For all other primes the order of different powers of 2 is different.

On a slightly different note, as bad as safe primes may sound for cryptography, they are still not as bad as strong primes.

21.4.17

Corporate AI

The internet is buzzing about a tool that one can use to supposedly determine how old they look. It supposedly uses "a proprietary blend of deep learning" and other AI buzz words.

Many are gushing about how amazing and magical this tool supposedly is so I thought I'd give it a try and see how it works.

20.4.17

In my previous entry I discussed a subset of safe primes with an interesting property.

It appears that when a prime p is of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes, then the order of each power of 2 mod p is phi(p)/2 where phi() is the Euler's Totient Function.

This is only one part of my conjecture. Here's another part of it:

Conjecture: If p is a prime of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes and n is an integer smaller than q such that it is not a power of 2 mod p, then the order of n mod p is phi(p)= p-1

Example: Below is an image of the exponentiation tables of Z23 and Z7.

In my previous entry I called such primes "steady primes". The reason why I chose the name "steady" is because of the "steady", uniform structure of the exponentiation table of Zp when p is a steady prime.

All elements of Zp when p is a steady prime have order that is equal to or greater than phi(p)/2. This is also true for the rest of the safe primes, which are the tough primes, but the structure of the exponentiation table of Zp when p is a tough prime is different.  With tough primes every odd power of 2 mod p has order p-1 and every even power of 2 mod p has order phi(p)/2.

Conjecture: If p is a steady prime, then phi(p)/2 is also a prime number.

Example: The first few steady primes are: 7,23,47,167,263,359,383,479,503

phi(p)/2 when p is the first few steady primes is equal to: 3,11, 23, 83, 131, 179, 191, 239, 261

Unfortunately, the curious properties of steady primes are not applicable to all products of steady primes. There are some products of steady primes pq with such uniform structure of the exponentiation table of Zpq but they are kind of rare.

Below is a calculator that can be used to generate powers of powers of integers modulo other integers, the algorithm for which I described here.

Another interesting subset of the set of safe primes is the set of steady primes as defined below:

Definition: A steady prime is a safe prime p such that all powers of 2 mod p have order phi(p)/2 where phi() is Euler's Totient Function.

Example:  Let p = 23.

Using a calculator, it is easy to see that all unique powers of 2 mod 23 are 2,4,8,16,9,18,13,3,6,12,1

Using another calculator, it is also easy to verify that the order of 2 mod 23, or the smallest integer k for which 2^k = 1 mod 23 is 11, the order of 4 mod 23 is also 11,  and so is the order of 8 mod 23, and this is the case for every other power of 2 mod 23 in the list above.

The first steady primes are 7,23,47,167,263,359,383,479,503,...

Conjecture: Steady primes are primes of the form 8p-1 such that 4p-1 and 8p-1 are also primes.

Claim: Given two steady primes p and q, the order of every power of 2 mod p*q is phi(p*q)/4

Claim: For all other safe primes q that are not steady primes, the order of at least one power of 2 mod q is at least 2 times less than the order of 2 mod q itself.

Below is a calculator for finding powers of any integer a mod n such that a < n.

26.3.17

Other Collatz-like Algorithms

I wrote about the Collatz conjecture in relation to finite fields and I came across a few interesting sequences but I didn't discuss the possibility of other Collatz-like algorithms that always reach 1.

Once again, the Collatz problem is defined as follows:

Collatz Algorithm: Given any positive integer n, let a0 = n. For i > 0, let:

ai = ai-1/2 if ai-1 is even
ai = 3*ai-1 + 1 if ai-1 is odd

Conjecture: Given any positive integer, the above recurrence relation returns 1.

This conjecture seems to hold although it hasn't been proven yet.

While looking at a different problem related to generating powers of 2 backwards, I stumbled upon a Collatz-like algorithm, which I generalize below for all positive integers.

Collatz-like Algorithm #1: Given any positive integer n, let a0 = (n+1)/2 if n is odd or a0 = n/2 if n is even. For i > 0, let:

ai = ai-1/2 if ai-1 is even
ai = (ai-1 - 1)/2 +  a0 if ai-1 is odd

Conjecture: Given any positive integer n, the above recurrence relation returns 1, and all integers it reaches before it reaches 1 are strictly less than n

In fact, I claim that:

Claim: If n is even then the Collatz-like Algorithm #1 generates all powers of 2 mod (n-1) in reverse order and if n is odd then it generates all powers of 2 mod n in reverse order.

Example: let n = 36 so a0 = 18
Then:
a1 = 18/2 = 9
a2 = ((9-1)/2) + 18 = 22
a3= 22/2 = 11
a4 = ((11-1)/2) + 18 = 23
a5 = ((23-1)/2) + 18 = 29
a6 = ((29-1)/2) + 18 = 32
a7 = 32/2 = 16
a8 = 16//2 = 8
a9 = 8/2 = 4
a10 = 4/2 = 2
a11 = 2/2 = 1

16.3.17

Ghetto Superstar

Last year I visited the world's oldest ghetto, namely the Venetian Ghetto Nuovo. It is the first place in the world where the word ghetto was used to describe a poor segregated community.

The Venetian Ghetto is a part of Venice, Italy where gondolas don't go. That's what I was told when I approached a gondolier asking for directions.

When both Apple maps and Google maps failed to provide a coherent path to my desired destination as well, I had to resort to ancient technology: ask a local who is not in the transportation industry.

A store clerk from a local souvenir shop kindly provided me with the following map, and I somehow managed to find my way.

Venice is by far the most surreal place that I had the opportunity to visit.
 An emergency vehicle
Many parts of the city are only accessible by boat, and only emergency service boats are allowed to speed.

According to my slightly cryptic but nevertheless useful map, I had to go to the Grand Canal first and take a waterbus in the opposite direction from where I was initially headed to until reaching the edge of the city.

 A waterbus stop near San Marco Square

The Grand Canal runs through the entire length of the Veneto region, which is composed of 117 small islands connected by bridges. The Venetian Ghetto is one of these islands.

 Rialto Bridge, Venice

I got off near (what looked like) the edge of the city and I went down a small street, then up another small street, and then I somehow ended up on one of the bridges connecting the Venetian Ghetto with the rest of Venice.

At the other side of the bridge there is a tunnel that leads to the main square. The Venetian ghetto was once home to thousands of Sephardic and Ashkenazi Jews, mostly refugees from other parts of Europe where they were unwanted at one point or another.

 Venetian Ghetto Nuovo

Although there was a Jewish presence in Venice for centuries prior to the establishment of the Venetian Ghetto, they were not segregated until Venice saw an influx of Jews from Spain after the Alhambra Decree and from other parts of Europe with similar sentiments at the time.

For many of the Sephardic Jews fleeing Spain, Venice was merely a pit stop before reaching the Ottoman Empire.

The Venetian Republic began rounding up and confining Jews to a small island on the edge of the Veneto region on the 29th of March 1516. The island was home to ancient foundries.

There are several synagogues in the ghetto tucked away in common areas of unassuming buildings, and some of them are still in use today. All of them honoured the Venetian Republic in some way with their decor in addition to honouring Ashkenazi, Sephardic, and Italian Jewish tradition.

 Sephardic Synagogue in the Venetian Ghetto: red and gold were the official colours of the Venetian Republic

The word ghetto as we know it today comes from an old Italian word for foundry pronounced as jetto (geto with a soft g as in jet). Apparently, the etymology of the word is a controversial topic but the most plausible theory is that Ashkenazi Jews had trouble pronouncing the soft g so they transformed it into a hard g effectively coining the word ghetto.

Life was not easy in the shanty part of town. Just like in the rest of the world at the time, Jewish people in the Venetian ghetto were only allowed to do the jobs that nobody else liked doing.

They were also not allowed to leave the ghetto at night and they had to wear identifiers that they were Jewish. Living quarters were cramped: large stories inside the buildings were separated into smaller ones to accommodate more people. Entire families were crammed inside single small rooms with low ceilings and sometimes no windows.

 The view above the main plaza across from Museo Ebraico di Venezia where I learned about the history of the Venetian Ghetto

Although people who spent time in the ghetto endured many hardships, some of them and many of their descendants thrived and prospered in different parts of the world.

Meanwhile in Spain 500 years after a bill was passed to expel all Jews from the Iberian peninsula, a new bill was introduced to grant citizenship to the descendants of those who were expelled. According to a DNA test I did, it is possible that I'm one such descendant.

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
.'.