Prime Intirety

Since ancient times humanity knew that there are infinitely many primes — though countable, writing a complete list of every prime is impossible if one intends to finish.
However, in practice one often only considers a minute subset of the naturals to work with and think about. When writing low-level languages like C, one is nearly forced to forget about almost every natural number — the data type u_int_32, for example, is only capable of representing \{\mathbb{N}_0\ni n<2^{32}\}.
Therefore, it is possible to produce a complete list of every prime representable in thirty-two bits using standard bit pattern interpretation — the entirety of the first 203\,280\,221 primes.

Generating said list took about two minutes on a 4GHz Intel Core i7 using an elementary sieve approach written in C compiled with gcc -O2.
All primes are stored in little-endian format and packed densely together, requiring four bytes each.

Using the resulting file, one can quickly index the primes, for example p_{10^7} = 179\,424\,691 = \text{ab1cdb3}_{16} (using zero-based indexing). Since each prime is stored using four bytes, the prime’s index is scaled by a factor of four, resulting in its byte index.

dd status=none ibs=1 count=4 if=primes.bin skip=40000000 | xxd 
00000000: b3cd b10a                                ....

Source code: intirety.c
Prime list: primes.bin (775.5 MiB)

Advertisements

Seventeen

Today it is the first day of July in the year 2017. On this day there is a point in time which can be represented as 1.7.2017, 17:17:17.
To celebrate this symbolically speaking 17-heavy day, I created a list of 17 integer sequences which all contain the number 17.
All sequences were generated using a Python program; the source code can be viewed below or downloaded. Because the following list is formatted using LaTex, the program’s plaintext output can also be downloaded.

  1. Prime numbers n.
    \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \dots\}
  2. Odd positive integers n whose number of goldbach sums (all possible sums of two primes) of n+1 and n-1 are equal to one another.
    \{5, 7, 15, 17, 19, 23, 25, 35, 75, 117, 177, 207, 225, 237, 321, 393, 453, 495, 555, 567, \dots\}
  3. Positive integers n who are part of a Pythagorean triple excluding 0: n^2=a^2+b^2 with integers a,b>0.
    \{5, 10, 13, 15, 17, 20, 25, 26, 29, 30, 34, 35, 37, 39, 40, 41, 45, 50, 51, 52, \dots\}
  4. Positive integers n where \lfloor (n!)^{\frac{1}{n}} \rfloor is prime
    \{4, 5, 6, 7, 8, 12, 13, 17, 18, 19, 28, 29, 33, 34, 35, 44, 45, 46, 49, 50, \dots\}
  5. Positive integers n with distance 1 to a perfect square.
    \{1, 2, 3, 5, 8, 10, 15, 17, 24, 26, 35, 37, 48, 50, 63, 65, 80, 82, 99, 101, \dots\}
  6. Positive integers n where the number of perfect squares including 0 less than n is prime.
    \{2, 3, 4, 5, 6, 7, 8, 9, 17, 18, 19, 20, 21, 22, 23, 24, 25, 37, 38, 39, \dots\}
  7. Prime numbers n where either n-2 or n+2 (exclusive) are prime.
    \{3, 7, 11, 13, 17, 19, 29, 31, 41, 43, 59, 61, 71, 73, 101, 103, 107, 109, 137, 139, \dots\}
  8. Positive integers n whose three-dimensional vector’s (n, n, n) floored length is prime, \lfloor \sqrt{3 \cdot n^2} \rfloor is prime.
    \{2, 3, 8, 10, 11, 17, 18, 24, 25, 31, 39, 41, 46, 48, 60, 62, 63, 76, 91, 100, \dots\}
  9. Positive integers n who are the sum of a perfect square and a perfect cube (excluding 0).
    \{2, 5, 9, 10, 12, 17, 24, 26, 28, 31, 33, 36, 37, 43, 44, 50, 52, 57, 63, 65, \dots\}
  10. Positive integers n whose decimal digit sum is the cube of a prime.
    \{8, 17, 26, 35, 44, 53, 62, 71, 80, 107, 116, 125, 134, 143, 152, 161, 170, 206, 215, 224, \dots\}
  11. Positive integers n for which \text{decimal\_digitsum}(n)+n is a perfect square.
    \{2, 8, 17, 27, 38, 72, 86, 135, 161, 179, 216, 245, 275, 315, 347, 432, 467, 521, 558, 614, \dots\}
  12. Prime numbers n for which \text{decimal\_digitsum}(n^4) is prime.
    \{2, 5, 7, 17, 23, 41, 47, 53, 67, 73, 97, 103, 113, 151, 157, 163, 173, 179, 197, 199, \dots\}
  13. Positive integers n where decimal_digitsum(2 \cdot n) is a substring of n.
    \{9, 17, 25, 52, 58, 66, 71, 85, 90, 104, 107, 115, 118, 123, 137, 142, 151, 156, 165, 170, \dots\}
  14. Positive integers n whose decimal reverse is prime.
    \{2, 3, 5, 7, 11, 13, 14, 16, 17, 20, 30, 31, 32, 34, 35, 37, 38, 50, 70, 71, \dots\}
  15. Positive integers n who are a decimal substring of n^n.
    \{1, 5, 6, 9, 10, 11, 16, 17, 19, 21, 24, 25, 28, 31, 32, 33, 35, 36, 37, 39, \dots\}
  16. Positive integers n whose binary expansion has a prime number of 1‘s.
    \{3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, \dots\}
  17. Positive integers n whose 7-segment representation uses a prime number of segments.
    \{1, 2, 3, 5, 7, 8, 12, 13, 15, 17, 20, 21, 26, 29, 30, 31, 36, 39, 47, 48, \dots\}

# Python 2.7.7 Code
# Jonathan Frech, 29th, 30th  of June 2017

Continue reading

A278328

The On-Line Encyclopedia of Integer Sequences (also known by its acronym, OEIS) is a database hosting hundreds of thousands of — as the name implies — integer sequences. Yet, despite the massive number of entries, I contributed a new integer sequence, A278328.

A278328 describes numbers whose absolute difference to their decimal reverse are square. An example would be 12 or 21 (both are the decimal reverse to each other), since \left|12-21\right|=9 and 9=3^2.

Not a whole lot is known about the sequence, partly due to its definition only resulting in the sequence when using the decimal system, though it is known that there are infinitely many numbers with said property. Since there are infinitely many palindromes (numbers whose reverse is the number itself), \left|n-n\right|=0 and 0=0^2.

Due to there — to my knowledge — not being a direct formula for those numbers, I wrote a Python script to generate them. On the sequence’s page, I posted a program which endlessly spews them out, though I later wrote a Python two-liner, which only calculates those members of the sequence in the range from 0 to 98 (shown below entered in a Python shell).


>>> import math
>>> filter(lambda n:math.sqrt(abs(n-int(str(n)[::-1])))%1 == 0, range(99))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 21, 22, 23, 26, 32, 33, 34, 37, 40, 43, 44, 45, 48, 51, 54, 55, 56, 59, 62, 65, 66, 67, 73, 76, 77, 78, 84, 87, 88, 89, 90, 95, 98]