Prime generating function

Question

Background

The Python code

((((((((n%35)^11)*195)|53)&181)+n)%168)*n)+83

produces 74 distinct primes for \$0 \le n \le 73\$. This code also works in Java. The operators are as follows:

• + is addition
• * is multiplication
• % is modulus
• & is bitwise AND
• | is bitwise OR
• ^ is bitwise XOR

The produced primes are: 83, 97, 113, 251, 311, 173, 197, 503, 571, 281, 313, 787, 863, 421, 461, 1103, 547, 593, 1361, 1451, 743, 797, 1733, 1831, 1931, 1033, 1097, 2243, 1231, 1301, 1373, 2687, 1523, 1601, 3041, 3163, 1847, 1933, 3541, 3671, 2203, 2297, 4073, 4211, 2591, 2693, 4637, 4783, 3011, 3121, 5233, 3347, 3463, 5701, 5861, 3823, 3947, 6353, 6521, 6691, 4463, 4597, 7213, 4871, 5011, 5153, 7937, 5443, 5591, 8501, 8693, 6047, 6203, 9281.

Task

Given an input integer \$n\$ output one of the primes from the above list, such that every output is distinct.

Rules

• \$n\$ will be between 0 and 73, inclusive.
• You can receive input through any of the standard IO methods.
• Leading zeroes are not allowed in output.
• This is code-golf, so shortest code in bytes wins!

Answer 1

x86 Machine Code, 23 bytes

86 89 C8 D4 23 34 0B 6B C0 C3 0C 35 24 B5 00 C8 D4 A8 F6 E1 83 C0 53 C3

Try it online!

The above bytes of code define a function that returns the \$n\$th prime, according to the formula given in the challenge. The function accepts a single argument, \$n\$, which is passed in the ECX register. It returns the result in the AX register. (Note: A 16-bit value is returned—the caller is responsible for zero-extending that 16-bit value in AX to a 32-bit value in EAX, if desired. Add one byte for a CWDE instruction if you think that is cheating!)

This is a custom calling convention, but it isn't particularly "weird", and machine/assembly language submissions are allowed to define a custom calling convention.

Credit where credit is due: this code is based on EasyasPi's x86 submission, but carefully optimized for size. In particular, I've chosen to target 32-bit x86 so that I can use the long-obsolete AAM instruction, which is not supported in x86-64 "long" mode. AAM was designed into the architecture as a way to convert from binary to binary-coded decimal (BCD). To do this, it divides the AL register by 10, storing the quotient in AH and the remainder in AL. (Note that this is the reverse of what the DIV instruction produces!) Intel's original manuals documented AAM as a one-byte instruction, but it was actually encoded with two bytes, where the second byte was 10—the divisor for AL. Changing that second byte to another value allows dividing AL by an arbitrary value, essentially giving x86 an instruction to divide by an 8-bit intermediate. This trick is used twice, to great effect. (There is also a complementary AAD instruction, which allows multiplying by an arbitrary 8-bit immediate value, but that did not result in any savings, since it actually performs the multiplication on AH, instead of AL, and the shift that is required to support that requires 2 bytes, plus the 2 bytes for AAD, which is more than the 3 bytes required to encode the IMUL reg, reg, imm.) There are myriad other size optimizations as well, compared to EasyasPi's code.

Here are the ungolfed assembly mnemonics:

            ; Input(s):
            ;   ecx = The zero-based index of the prime to generate (i.e., "n").
            ;         (Note: This is assumed to be a value from 0 to 73.)
            ; Output(s):
            ;   ax  = The nth prime.
            ;         (Note: This is a 16-bit unsigned integer;
            ;                caller must zero-extend if desired.)
            ; Clobbers:
            ;   eax, flags
            GenerateNthPrime:
89 C8         mov   eax, ecx       # make a copy of the input (ecx) in eax
D4 23         aam   35             # al %= 35        ; ah = al / 35
34 0B         xor   al, 11         # al ^= 11
6B C0 C3      imul  eax, eax, -61  # ax  = (al * 195)
0C 35         or    al, 53         # al |= 53
24 B5         and   al, 181        # al &= 181
00 C8         add   al, cl         # al += cl
D4 A8         aam   168            # al %= 168       ; ah = al / 168
F6 E1         mul   cl             # ax  = (al * cl)
83 C0 53      add   eax, 83        # ax += 83
98          # cwde                 # eax = ax (sign-extend, assuming sign bit is 0)
C3            ret

Note the cwde instruction immediately before the return instruction there, which is commented out. For the purposes of this submission, this instruction is functionally equivalent to movzx eax, ax, which is what the caller of this function would normally use to zero-extend its 16-bit result (ax) to a 32-bit result (eax). However, cwde is encoded in only 1 byte, as opposed to the 3 bytes required by movzx. As I mentioned above, if you don't think it's legit that I return a 16-bit result, then add the cwde instruction to increase the total size of the function by only one byte.

Answer 2

JavaScript (ES6),  38  36 bytes

Saved 2 bytes thanks to @tsh

A slightly size-optimized version of the original formula.

n=>(((n%35^11)*6.09&4?13:53)+n)*n+83

Try it online!

Answer 3

05AB1E, 23 22 21 bytes

^{-1 byte thanks to Command Master}

The first part of the code is shorter when replaced by a binary lookup table.

•4àт©Á•bsè40*13++*83+

Try it online!

Answer 4

Retina 0.8.2, 168 166 bytes

.+
$*1¶$&$*
\G1{35}

^((1{16})*)(1{8}|())(1{4})?(11|())(1|())
$1$#4$*8$*1$5$#7$*2$*1$#9$*
\G1
195$*
1{256}

(1{128})?1*¶
$1$'53$*1¶
1{168}

1(?=1*¶(1*))
$1
¶1*
83$*
1

Try it online! Link includes test suite that generates the results for n=0..73. Based on @Arnauld's rearrangement that reduces the bitwise or into an addition. Explanation:

.+
$*1¶$&$*

Make two unary copies of n.

\G1{35}

Reduce modulo 35.

^((1{16})*)(1{8}|())(1{4})?(11|())(1|())
$1$#4$*8$*1$5$#7$*2$*1$#9$*

Bitwise Xor with 11. This is done by breaking the number down into a multiple of 16 plus optional matches of 8, 4, 2 and 1, adding 8, 2, and 1 only when the corresponding match is absent in the original number.

\G1
195$*

Multiply by 195.

1{256}

(1{128})?1*¶
$1$'53$*1¶

Bitwise And with 128 (implemented via %256/128*128) and add on 53 and n.

1{168}

Reduce modulo 168. (No \G is necessary as n is less than 168.)

1(?=1*¶(1*))
$1

Multiply by n.

¶1*
83$*

Add 83 and remove the copy of n.

1

Convert to decimal.

Answer 5

C (gcc), 43 bytes

f(n){n=('v3ff'>>n%35%31&1?13+n:53+n)*n+83;}

Try it online!

Tio link based on noodle9's post.

Answer 6

J, 40 bytes

83+]*168|]+181 AND 53 OR 195*11 XOR 35|]

Try it online!

Boring translation of formula. But nice demo of J's "evaluate right to left / read out loud left to right" property:

• 83 plus input times 168 divided into input plus 181 bitwised and with 53 bitwised or with 195 times 11 xor'd with 35 divided into input.

Answer 7

Charcoal, 38 bytes

ＮθＩ⁺⁸³×θ⁺θ⎇＆¹²⁸×¹⁹⁵⁻｜¹¹﹪θ℅#＆¹¹﹪θ℅#¹³℅5

Try it online! Link is to verbose version of code. Explanation: Basically a translation of the original expression, except for the following changes:

• Where possible, the arguments to operators were reversed, to avoid placing numeric constants consecutively
• Otherwise some numeric constants calculated using ASCII codes to avoid consecutive numeric constants
• No bitwise XOR, so calculated longhand
• @tsh's ternary idea on his comment to @Arnauld's answer turned out to be the shortest way to choose between 13 and 53.

Ｎθ                                      Input `n`
                       ﹪θ℅#   ﹪θ℅#      `n` modulo ASCII code 35 of literal `#`
                    ｜¹¹                 Bitwise Or with literal `11`
                           ＆¹¹          Bitwise And with literal `11`
                   ⁻                    Subtract, giving the bitwise Xor
               ×¹⁹⁵                     Multiply by literal `195`
           ＆¹²⁸                         Bitwise And with literal `128`
          ⎇                             If nonzero
                                  ¹³    Then literal `13`
                                    ℅5  Else ASCII code 53 of literal `5`
        ⁺θ                              Add `n`
      ×θ                                Multiply by `n`
   ⁺⁸³                                  Add literal `83`
  Ｉ                                     Cast to string
                                        Implicitly print

Answer 8

x86_64, 33 bytes

89 c1 b2 23 f6 f2 80 f4  0b b0 c3 f6 e4 0c 35 66
25 b5 00 01 c8 b2 a8 f6  f2 86 c4 f6 e1 83 c0 53
c3                

        .intel_syntax noprefix
        # in: eax (zero extended)
        # out: eax
        .globl primegen
primegen:
        mov     ecx, eax
        mov     dl, 35
        div     dl
        xor     ah, 11
        mov     al, 195
        mul     ah
        or      al, 53
        and     ax, 181
        add     eax, ecx
        mov     dl, 168
        div     dl
        xchg    al, ah
        mul     cl
        add     eax, 83
        ret

Try it online!

Nothing special, it is pretty much a direct translation of the example code.

Answer 9

Jelly, 26 25 bytes

%35^11×195&Ø⁷+53+%168×+83

Try it online!

-1 thanks to the default.

Answer 10

FALSE, 57 bytes

[[$2ø\/*-]m:$$35m;!11$2ø~&@@~&|195*53|181&+168m;!*83+.]

Try it online!

Function that takes a number as input.

Explanation:

[$2ø\/*-]m: {Define modulo function as m (a - (n * trunc(a/n)))}
    $2ø {Duplicate both a and n to have the stack be a, n, n, a}
    \/ {swap n and a and divide, which auto-truncates}
    *- {then multiply by n and subtract a by everything} 
$$35m;!11$2ø~&@@~&|195*53|181&+168m;!*83+. {Prime generation}
    $$ {duplicate n twice because we need to add and multiply by n later on}
    35m;! {n % 35}
    11$2ø~&@@~&| { ^ 11 (xor has be done as (not a and b) or (a and not b) as there is no built-in in FALSE)}
        $2ø {get stack to be a, b, b, a}
        ~&@@ {do b and not a, and rotate twice, stack is now result, a, b}
        ~&| {then do a and not b and or the results together to finish the xor}
    195* { * 195}
    53| { | 53}
    181& { & 181}
    + { + n}
    168m;! { % 168}
    * { * n}
    83+ { + 83}
    . {output resulting prime}

Answer 11

Pyth, 30 bytes

+83*%+.&181.|*195x%Q35hT53Q168

Try it online!

Answer 12

MathGolf, 22 bytes

I6E6V057]yâ§Z⌠*C++*Zx+

Port of @theDefault.'s 05AB1E answer, so make sure to upvote him/her as well!

Try it online.

Explanation:

I                      # Push 20
 6                     # Push 6
  E                    # Push 15
   6                   # Push 6
    V                  # Push 34
     0                 # Push 0
      5                # Push 5
       7               # Push 7
        ]              # Wrap all values on the stack into a list
         y             # And join them together: 20615634057
          â            # Convert it from an integer to a binary-list:
                       #  [1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1]
           §           # (0-based) index the (implicit) input-integer into this list
            Z⌠         # Push 38, and increment it by 2 to 40
              *        # Multiply the current value by this 40
               C+      # Add 13
                 +     # Add the (implicit) input-integer
                  *    # Multiply it by the (implicit) input-integer
                   Zx  # Push 38, and reverse it to 83
                     + # Add this 83 to the value
                       # (after which the entire stack joined together is output implicitly)

---

MathGolf doesn't contain any builtins for bitwise-AND, OR, nor XOR. But even if it did, this approach above would still be 2 bytes shorter than implementing the formula in the challenge description would have been:

24 bytes:

W%A^CE**Wx|G1§&+BD*%*Zx+

Explanation:

W%                       # Modulo the (implicit) input-integer by 35
  A^                     # Bitwise-XOR by 11
                         # (assuming `^` would have been a bitwise-XOR builtin)
    CE*                  # Push 13, push 15, multiply them together to 195
       *                 # Multiply the value by this 195
        Wx               # Push 35, reverse it to 53
          |              # Bitwise-OR by this 53
                         # (assuming `|` would have been a bitwise-OR builtin)
           G1§           # Push 18, push 1, concatenate them together to 181
              &          # Bitwise-AND by this 181
                         # (assuming `&` would have been a bitwise-AND builtin)
               +         # Add the (implicit) input-integer
                BD*      # Push 12, push 14, multiply them together to 168
                   %     # Modulo by this 168
                    *    # Multiply to the (implicit) input-integer
                     Zx  # Push 38, reverse it to 83
                       + # Add this 83 to the value
                         # (after which the entire stack joined together is output implicitly)

Answer 13

C# (Visual C# Interactive Compiler), 38 bytes

n=>(((n%35^11)*195)&181|53+n)%168*n+83

I just removed all the paracenteses I could.

Try it online!

Answer 14

C (gcc), 48 46 bytes

Saved 2 bytes thanks to Neil!!!

f(n){n=((((n%35^11)*195&128)+53+n)%168*n)+83;}

Try it online!

Simple port.

Answer 15

Perl 5 -p, 43 bytes

$_=(((($_%35^11)*195|53)&181)+$_)%168*$_+83

Try it online!