[mawvhdtz] permutation by primes

we permute the numbers 1..n using the randomness of the prime numbers.

there are many ways to do this.  we implement the "inside-out" variation of the Fisher-Yates shuffle.  the index "c" chains iterations of the loop, because it feels like that would make things more "random". we transform primes by p=(p-1)/2 to prevent them from being all odd.  because the i-th prime is approximately i*log(i), c will cycle around (because of mod) about log(i)/2 times each iteration.

u(n) = my(a=vector(n)); my(c=0); for(i=1, n, my(p=prime(i)); if(2==p, p=0, p=(p-1)/2); c+=p; c%=i; j=c+1; a[i]=a[j]; a[j]=i); a;

note that vectors in Pari/GP are 1-indexed and initialized to zero.  we are permuting numbers 1 through n, so if we were to see a zero in the output, an uninitialized value has gotten through, i.e., there is a bug.  the nthprime function is also 1-indexed, i.e., prime(1)=2 .

here is the permutation of numbers 1 through 30:

u(30)

[3, 10, 29, 6, 18, 15, 28, 21, 5, 27, 17, 12, 26, 20, 25, 16, 24, 7, 19, 11, 23, 1, 9, 8, 13, 14, 2, 4, 30, 22]

step by step: the newest number each iteration is underlined.

i	prime(i)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
1	2	1
2	3	1	2
3	5	3	2	1
4	7	3	2	1	4
5	11	3	2	1	5	4
6	13	3	2	1	6	4	5
7	17	3	2	1	6	7	5	4
8	19	3	2	1	6	7	8	4	5
9	23	3	2	1	6	7	8	4	9	5
10	29	3	10	1	6	7	8	4	9	5	2
11	31	3	10	1	6	7	11	4	9	5	2	8
12	37	3	10	1	6	7	11	4	9	5	2	8	12
13	41	3	10	1	6	7	13	4	9	5	2	8	12	11
14	43	3	10	1	6	7	13	4	9	5	2	8	12	14	11
15	47	3	10	1	6	7	15	4	9	5	2	8	12	14	11	13
16	53	3	10	1	6	7	15	4	9	5	2	8	12	14	11	13	16
17	59	3	10	1	6	7	15	4	9	5	2	17	12	14	11	13	16	8
18	61	3	10	1	6	18	15	4	9	5	2	17	12	14	11	13	16	8	7
19	67	3	10	1	6	18	15	4	9	5	2	17	12	14	11	13	16	8	7	19
20	71	3	10	1	6	18	15	4	9	5	2	17	12	14	20	13	16	8	7	19	11
21	73	3	10	1	6	18	15	4	21	5	2	17	12	14	20	13	16	8	7	19	11	9
22	79	3	10	22	6	18	15	4	21	5	2	17	12	14	20	13	16	8	7	19	11	9	1
23	83	3	10	22	6	18	15	4	21	5	2	17	12	14	20	13	16	8	7	19	11	23	1	9
24	89	3	10	22	6	18	15	4	21	5	2	17	12	14	20	13	16	24	7	19	11	23	1	9	8
25	97	3	10	22	6	18	15	4	21	5	2	17	12	14	20	25	16	24	7	19	11	23	1	9	8	13
26	101	3	10	22	6	18	15	4	21	5	2	17	12	26	20	25	16	24	7	19	11	23	1	9	8	13	14
27	103	3	10	22	6	18	15	4	21	5	27	17	12	26	20	25	16	24	7	19	11	23	1	9	8	13	14	2
28	107	3	10	22	6	18	15	28	21	5	27	17	12	26	20	25	16	24	7	19	11	23	1	9	8	13	14	2	4
29	109	3	10	29	6	18	15	28	21	5	27	17	12	26	20	25	16	24	7	19	11	23	1	9	8	13	14	2	4	22
30	113	3	10	29	6	18	15	28	21	5	27	17	12	26	20	25	16	24	7	19	11	23	1	9	8	13	14	2	4	30	22
i	prime(i)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30

note that the inside-out algorithm can be run incrementally, so terminating the algorithm at any step above would result in a permutation of a fewer number of elements.

permuting the digits 0 through 9 yields 2905673841.  permuting the letters a through z yields cjvfroduebqlztypxgskwaihmn.

motivation is a puzzle that requires solving the Riemann Hypothesis.  consider using the above permutation (and additional permutations generated similarly) in a substitution-permutation cipher.

how random are these permutations?  although we've corrected for the bias against even numbers, primes not being multiples of each other likely introduces other biases.  what other structures that look approximately uniformly random can be constructed from the primes?  (previously, bitmaps of gradually decreasing density.)  if we first produce a good cipher, then anything is possible.