Long period primes

Question

A long period prime is a prime number \$p\$ such that decimal expansion of \$1/p\$ has period of length \$(p-1)\$. Your task is to output this number sequence. For purposes of this challenge we will consider only odd primes.

Period of a decimal expansion of a rational number is the smallest period \$k\$ that makes the decimal representation periodic (repeating at regular intervals \$k\$).

This is A001913, or A006883 without leading \$2\$.

Examples

\$\frac{1}{3}=0.33333\ldots\$, so the period is \$1\$ (although the number is also 2-periodic, 3-periodic etc., but we take the minimum). \$3-1=2\neq1\$, so \$3\$ won't appear in our sequence.

\$\frac{1}{7}=0.14285714\ldots\$ - the period is \$6 = 7-1\$.

Rules

This is a standard code-golfsequence challenge, so please comply with the defaults.

With floating point errors, let's stick to the highest voted decisive answer here on meta, so I'll allow them.

Test cases

First 10 entries:

7, 17, 19, 23, 29, 47, 59, 61, 97, 109

For more visit: A001913's b-file.

---

Inspired by recent Numberphile video.

Answer 1

x86-64 machine code, 27 bytes

31 F6 FF C6 89 F1 6A 0A 58 99 F7 FE 6B C2 0A FF CA E0 F6 E2 ED FF CF 75 E9 96 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a number \$n\$ in EDI and returns the 1-indexed \$n\$th long-period prime in EAX.

In assembly:

f:
    xor esi, esi        # Set ESI to 0.
nextm:
    inc esi             # Add 1 to ESI to get the next number (m) to test.
    mov ecx, esi        # Set ECX to m.
    push 10             # Push 10 onto the stack
    pop rax             #  and pop it into RAX.
l:
    cdq                 # Sign-extend, setting up for the next instruction.
    idiv esi            # Divide by m, putting the quotient in EAX and the remainder in EDX.
    imul eax, edx, 10   # Set EAX to EDX×10.
    dec edx             # Subtract 1 from EDX.
    loopnz l            # Subtract 1 from ECX, and repeat if both are nonzero.
    loop nextm          # Subtract 1 from ECX, and jump if the result is nonzero.
                        #   This point will be reached iff 1 is first obtained
                        #   after exactly m-1 iterations of ×10 and mod m.
    dec edi             # Subtract 1 from EDI, counting down from n.
    jnz nextm           # Jump if it is nonzero.
    xchg esi, eax       # Exchange the final value of m from ESI into EAX.
    ret                 # Return.

Answer 2

Python 3, 73 64 bytes

The usual Wilson's theorem based prime generation combined with computing the multiplicative order. Now porting tsh's answer, you don't actually need to check for primality if the multiplicative order is right.

k=3
while j:=1:
 while 10**j%k>1<k>j:j+=1
 j==k-1==print(k);k+=1

Try it online!

Answer 3

JavaScript + alert, 57 bytes

for(i=2n;++i;j-i||alert(i))for(j=1n;j<=i&10n**j++%i!=1;);

Try it online!

Answer 4

Husk, 15 bytes

tfλ=←⁰LUm%⁰İ⁰)N

Try it online!

For each natural number (N), get the series of powers-of-10 (İ⁰) modulo that number (m%⁰); now select those (fλ)) for which the length (L) of the longest prefix of unique elements (U) is equal to (=) that number minus one (←⁰). This annoyingly includes 2 at the start, so we need to take the tail (t).

Answer 5

Jelly,  12  11 bytes

ṖȯfƑ⁵*Ɱ%Ɗµ#

A full program that accepts an integer, n, from STDIN and prints the Jelly representation* of a list of the first n numbers which have a primitive root of \$10\$.

Try it online!

^{* the Jelly representation of a list with a single element is just that element.}

How?

ṖȯfƑ⁵*Ɱ%Ɗµ# - Main Link: no arguments
         µ# - implicitly takes input - call this N
         µ# - collect the first N values of K (in [0,1,2,...]) for which:
Ṗ           -   pop -> [1,2,...,K-1]
 ȯ          -   logical OR with K (so we get K when K is 0 or 1, rather than [])
                (let's call this list of integers (or 0 or 1) P)
        Ɗ   -   last three links as a monad - f(K):
    ⁵       -     10
      Ɱ     -     map across (implicit [1,2,...,K]) with:
     *      -       exponentiation
       %    -     modulo K (vectorises)
                (let's call this list of integers M)
   Ƒ        -   is P invariant under?:
  f         -     P filter keep M
            - implicit print

---

A couple of other 11 byters:

⁵*Ɱ%i1=ṖṪµ#
⁵*Ɱ%=1Ḅ⁼2µ#

Answer 6

Factor + lists.lazy math.primes.lists project-euler.026, 57 52 bytes

[ lprimes [ dup -1 ^ period-length - 1 = ] lfilter ]

Try it online!

Believe it or not, Factor includes solutions to the first 200 or so Project Euler problems and exposes them the same way as any other vocabulary. Many of these vocabularies provide useful words, such as project-euler.026 which provides the period-length word.

Explanation

It's a quotation that outputs the infinite lazy sequence of long period primes.

• lprimes An infinite lazy list of primes.
• [ ... ] lfilter Select only those whose...
• dup -1 ^ period-length - 1 = ...reciprocals have a period length one less.

Answer 7

05AB1E, 12 bytes

∞ʒ©L.Δ°®%}®α

Port of @tsh's JavaScript answer, and also outputs the infinite sequence.

Try it online.

Explanation:

∞          # Push an infinite positive list: [1,2,3,...]
 ʒ         # Filter it by:
  ©        #  Store the current value in variable `®` (without popping)
   L       #  Pop and push a list in the range [1,®]
    .Δ     #  Find the first value in this list which is truthy for:
      °    #   Push 10 to the power the value
       ®%  #   Modulo-`®`
           #   (Note: only 1 is truthy in 05AB1E)
     }     #  After we've found our result (or not, resulting in -1)
      ®α   #  Take the absolute difference with `®`
           #  (and again, only 1 is truthy in 05AB1E)
           # (after which the infinite list is output implicitly)

Answer 8

R, 53 51 bytes

repeat if(T==match(1,10^(1:(T=T+1))%%T,0))cat(T,"")

Try it at rdrr.io (but see below...)

Similar approach to this: for each integer T, check whether the first 1 in the list of powers-of-10 modulo T occurs at the T-1-th position (meaning that the period of the decimal expansion is T-1).

Unfortunately, this approach suffers (quite badly) from inaccuracies as soon as the powers-of-10 exceed R's floating-point precision: so, it only manages to output 7 17 19 23 before generating a large number of probable complete loss of accuracy in modulus warnings.

---

R, 65 bytes

repeat{y=T=T+1;z=1;while(y&(z=(z*10)%%T)-1)y=y-1;cat(T[y==2],"")}

Try it online!

Alternative approach unaffected by floating-point inaccuracies (at least until very large values...); outputs a whitespace-separated list of all long-period-primes.

Answer 9

Vyxal, 11 bytes

Þp'ɾ↵$%1ḟ⇧=

Try it Online!

Port of Kevin Cruijssen's answer.

Þp'         # Filter the infinite list of primes by...
   ɾ        # 1...n
    ↵       # 10 to the power of each of those
     $%     # Modulo n
       1ḟ   # Find the first index of a 1
         ⇧= # Is it + 2 equal to n?

See, when I saw something about "powers of 10 modulo n" I thought it meant you could get something with an equivalent cycle in that way. I didn't realise it was so simple...

Answer 10

Ruby, 47 bytes

7.step{|x|x-1==(1..x).find{|c|10**c%x<2}&&p(x)}

Try it online!

Answer 11

Wolfram Language (Mathematica), 52 bytes

If[10~MultiplicativeOrder~k==k-1,Print@k]~Do~{k,∞}

Try it online!

-15 bytes from @ovs

Answer 12

Javascript + alert, 54 53 bytes

for(n=3;i=n++;i||alert(n))for(x=1;i*(x=x*10%n)>i--;);

Answer 13

C (gcc), ^{73 72} 71 bytes

k,j,i;f(n){for(j=k=2;n-=j==k++-1;)for(i=10,j=0;j++<k&i%k>1;)i*=10;--k;}

Try it online!

Returns the \$1\$-based \$n^\text{th}\$ long period prime.

Answer 14

Charcoal, 29 bytes

≔¹θＦＮ«≦⊕θＷ›⊖θ⊕⌕﹪Ｘχ…¹θθ¹≦⊕θ⟦Ｉθ

Try it online! Link is to verbose version of code. Outputs the first n long period primes. Explanation: Based on @tsh's answer.

≔¹θ

Start at 2 (because we increment this almost immediately). (Any number below 7 would work.)

ＦＮ«

Loop n times.

≦⊕θ

Increment the number under test.

Ｗ›⊖θ⊕⌕﹪Ｘχ…¹θθ¹

While the number's period is not equal to one less than it...

≦⊕θ

... increment the number under test.

⟦Ｉθ

Output the next long period prime.

Answer 15

Zsh, 54 bytes

for ((;++n;))(r=9;for ((;r%n;))r+=9
((n+~$#r))||<<<$n)

Attempt This Online!

Uses the fact that the repeating decimal period of \$ n \$ is the minimum integer \$ i \$ such that \$ n \$ divides \$ r = 10^i - 1 = \operatorname{rep}(9, i)\$.

Prints the sequence infinitely, but can only manage the first 3 terms before Zsh's floating point numbers implode.

We have to be careful with how and where we use $r to ensure it stays a string, so that r+=9 literally appends instead of adds 9.