How to calculate the value of the biggest prime we know?

I hope that I don’t need to introduce prime numbers to anyone. They are fascinating for all mathematic enthusiasts. We know a lot of prime numbers, but we have no formula to calculate them. Search for the biggest primes is an ongoing competition. People are looking for the biggest primes among the so-called Mersenne Primes. Mersenne Primes are primes that can be expressed as 2n-1. The record is currently held by 282,589,933−1 with 24,862,048 digits, found by GIMPS in December 2018 (more on Wikipedia).

We can find a value of 282,589,933-1 online (for example beginning and the end of the number on Wikipedia linked above). But what if we would like to calculate the value ourselves? We have multiple options. For the sake of this article, I selected 2:

bc – an arbitrary precision calculator language

bc is a linux/unix command line calculator that supports arbitrary precision:

We can run the following in the terminal to calculate the value of 282,589,933-1. We use tr and sed to pack the result in one line.

echo "Testing BC:"
time echo "2^82589933-1" \
    | bc \
    | tr "\n" " " \
    | sed 's/\\ //g' \
    > bc.txt


Since the calculation is not trivial the answer is not coming instantaneously. On my 2021 MacBook pro with M1 Max processor it took 30 minutes to get the result: >24 megabytes of digits.

Python

Yes, Python! Python supports arbitrary precision integers by default. There is a slight complication that was added recently for security reasons: we need to increase the default length of the number that can be converted to a string. Let’s consider the following code:

import sys
sys.set_int_max_str_digits(int(3e7))

number = 82589933

print(2**number-1, end=' ')

And run it in the terminal:

echo "Testing Python":
time python python.py > python.txt

It takes python almost 3 hours to compute the result.

Results

Finally, we can confirm that both results are the same:

echo "Comparing Results":
shasum bc.txt
shasum python.txt

Which should give result as following:

Comparing Results:
9abebcdaf11efd28f1797d6b2744cbcb0cc66e52  bc.txt
9abebcdaf11efd28f1797d6b2744cbcb0cc66e52  python.txt

Summary

If you ever need to calculate integers bigger then 64 or 128 bits, now you know how.

| comments

Passion for data and plane travel

I’m very enthusiastic about both data science and plane travel. I found a way of combining these two passions. It stared from my frequently visiting flight tracking websites like adsbexchange.com or flightradar24.com. The next step for me was to build my own ADS-B receiver using Raspberry Pi. I stared with small antenna by the windows and quickly changed my setup to use big antenna on the top of my house. My Raspberry collects and shares data for over 8 years now (that reminds me, that I’ve never updated it). It receives signals from planes as far as 250 miles from my house. I’ve done some interesting data science using this data, but quickly realized that I’m hungry for more data.

Over 4 years ago I had an idea to start collecting data about all planes around the globe and storing it in the database for future science. I spend time searching for data sources, designing the database and all related processes and finally started collecting data. I started collecting data in November 2018.

Today, almost 4 years later I have a decent database to play with. The database is over 16 billion rows (1.6e10) and occupies almost 3 TB of disk space. I’m using Google BigQuery to store the data ans Docker to run the whole related infrastructure.

I’m going to share some of the most interesting analysis I was able to do with this data. I hope you will find it interesting and maybe even useful. Stay tuned!

| comments

GMT (Generic Mapping Toolbox) in Docker

GMT (Generic Mapping Toolbox) is a very powerful tool for making maps. It is primarily a command line tool that creates Post Script files (yes, sound like very old times, but still powerful). It is available from the GMT website. GMT was created and is still maintained by Paul Wessel at the University of Hawai’i at Mānoa. My first GMT experience dates back to ~2010, when I was a Masters student.

Fun Fact: In mid 2010s I applied for Post Doc postion at the University of Hawai’i at Mānoa. I was very excited about the opportunity to work with Paul Wessel. Unfortunately, I didn’t get the position, but it was close!

I recently decided to try GMT again, and to save time on installation and configuration I decided to use Docker. I tried to find ready to use container with GMT, but finally decided to create my own. I’m sharing my Dockerfile and instructions on GitHub: https://github.com/gozwei/gmt-docker.

I’m going to use this container to create maps for my blog. I’m going to share the code and maps in the future posts. Stay tuned!

Quick usage instructions:

I will assume that you have Docker installed on your computer. If not, please follow the instructions on the Docker website.

Clone to repository and build the container:

        
docker build -t gmt:6.4.0 .
        

Create an alias (optional, recommended if you are using Linux or MacOS – have no idea how to do that on Windows):

        
alias gmt-docker='docker run --rm -v "$PWD/:/root/work/" -i -t gmt:6.4.0'
        

This will allow you to use the container anywhere on your computer – this is useful, because you need to map your current directory to the container to use it.

Now you can use the container. For example, to create a map of the USA you can use the following commands:

        
gmt-docker gmt set FONT_ANNOT_PRIMARY 5p,Helvetica
gmt-docker gmt psbasemap -R-128/-65/24/51 -Jl-96.5/40/23/52/1:40000000 -B10g2 -K -P > USA.ps
gmt-docker gmt pscoast -R -Df -Ia/0.03p,black -J -N1/0.5p -N2/0.25p,- -G#dde6d5 -S#a5bfdd -A0/0/4 -W0.5p,black -O -P >> USA.ps
gmt-docker convert -geometry 2048x2048 -density 600 -background white -flatten -trim +repage USA.ps USA.png
        

This will create a map of the USA and save it as USA.png. The map will look like this:

Disclaimer: The purpose of this post is not to teach GMT or Docker. I’m just sharing my experience with these tools. If you want to learn more about GMT, please visit the GMT website. If you want to learn more about Docker, please visit the Docker website. I just hope I can make your journey with these tools a little bit easier.

I hope you will find this useful. If you have any questions, please let me know in the comments.

| comments

Plotting maps in Python

Python is great for processing and visualizing data. Today I’d like to share simple tips around plotting data on map using Python.

Let’s consider following example: I want to plot a map of airports around the world. Data for the airports can be obtained from OpenFlights:

        
from io import StringIO
import pandas as pd
import requests

csvString = requests.get("https://raw.githubusercontent.com/jpatokal/openflights/master/data/airports.dat").text
csvStringIO = StringIO(csvString)
airports = pd.read_csv(csvStringIO, sep=",", header=None)
        

This will download the data and create a Pandas DataFrame. We can plot airport locations:

        
import matplotlib.pyplot as plt

ax = plt.subplot(1,1,1)
ax.plot(airports[7], airports[6], 'r.', ms=.5)
plt.axis([-180, 180, -90, 90])
        



Nice plot, but not really a map yet. We need to add some contours. A Global Self-consistent, Hierarchical, High-resolution Geography Database (GSHHG) is a good place to start. You can get data and more info here: http://www.soest.hawaii.edu/pwessel/gshhg/. I recommend downloading “GSHHG coastlines, political borders and rivers in shapefile format (zip archive)”. Now we can plot much nicer map:

        
import geopandas as gp
import matplotlib.pyplot as plt

coastline = gp.read_file('/media/RAID/DATA/GSHHG_2.3.7/GSHHS_shp/f/GSHHS_f_L1.shp')
ax = plt.subplot(1,1,1)

coastline.boundary.plot(ax=ax, edgecolor='black', lw=0.5)

ax.plot(airports[7], airports[6], 'r.', ms=.5)
plt.axis([-180, 180, -60, 85])
        



Or going one step further:

        
import geopandas as gp
import matplotlib.pyplot as plt

coastline = gp.read_file('/media/RAID/DATA/GSHHG_2.3.7/GSHHS_shp/c/GSHHS_c_L1.shp')
borders = gp.read_file('/media/RAID/DATA/GSHHG_2.3.7/WDBII_shp/c/WDBII_border_c_L1.shp')

lakes = gp.read_file('/media/RAID/DATA/GSHHG_2.3.7/GSHHS_shp/c/GSHHS_c_L2.shp')

ax = plt.subplot(1,1,1)

coastline.boundary.plot(ax=ax, edgecolor='black', lw=0.5)
borders.plot(ax=ax, edgecolor='black', lw=0.25)
lakes.boundary.plot(ax=ax, edgecolor='black', lw=0.25)

ax.plot(airports[7], airports[6], 'r.', ms=.5)
plt.axis([-180, 180, -60, 85])
        



Note that in the last example we used “crude resolution” of the coastline and borders – we don’t need much detail for a map in such scale.

Another source of shapefiles with borders that I recommend is GADM. You might be interested in looking at one of my public repositories for more details: GADM-consolidated-shapefile.

| comments

Generating images with LaTeX equations

Sometimes it is useful to generate an image (like a PNG file) with a high-resolution mathematical equation. I know that there are online tools for doing that but imagine you are like me and prefer getting things done “in-house”.

I will assume you have docker available (if not, go to https://www.docker.com/ and install Docker Desktop).

In the first step we will need to get two images from Docker Hub (we do that in terminal / command line):

docker pull miktex/miktex
docker pull dpokidov/imagemagick

Both commands will download some stuff and should be ready in a minute or so. Now we will need our LaTeX code that defines the equation:

\documentclass{article}
\usepackage{amsmath}
\pagenumbering{gobble}
\begin{document}
\begin{equation*}
e^{i\pi }+1=0
\end{equation*}
\end{document}

Now assuming that the LaTeX code is saved in test.tex file we will need to execute 3 steps:

docker run --rm -v miktex:/miktex/.miktex -v $PWD:/miktex/work miktex/miktex latex test.tex
docker run --rm -v miktex:/miktex/.miktex -v $PWD:/miktex/work miktex/miktex dvipng -D 600 -bg Transparent test.dvi
docker run --rm -v $PWD:/imgs dpokidov/imagemagick imgs/test1.png -trim imgs/test2.png

The first command uses miktex/miktex Docker Image to “compile” out LaTeX file to DVI format.

The second command uses the same Docker Image to convert DVI into PNG image. Our LaTeX document has one page, so one PNG will be created after conversion (test1.png). Unfortunately, we are not done yet, because our PNG image has strange margins.

In the last step, we fix those margins by using dpokidov/imagemagick Docker Image. Our final result looks like this (test2.png):

| comments

Older posts »