# Numbers x such that x^2 divides 7^x-1

There is a set of numbers x, such that x^2 divides 7^x-1.

Your task is to find these numbers. Given an input of n, the code will print the nth number that follows this rule.

# Examples 1-index

In   Out
3    3
9    24
31   1140

The relevant sequence can be found here.

## Rules

Shortest answer will be the winner*

Standard golfing rules apply

Loopholes are not allowed

• @nimi I wrote these down when planning and never implemented them. I've updated the question Commented Jan 19, 2017 at 20:55
• What are the limits of n? I can give the correct result with n=9, but n=10 is already causing me problems. Commented Jan 19, 2017 at 21:49
• @briantist If you're getting the wrong result for higher input values, your answer is wrong. If it's just taking a long time, that can be implementation dependent. Commented Jan 19, 2017 at 21:50
• It's not just taking a long time. n=10 gives me 32; it's because it starts using double instead of integers and the mod is wrong after that. :( Commented Jan 19, 2017 at 21:56

([x|x<-[1..],mod(7^x-1)(x^2)<1]!!)

This uses 0-based indexing. Usage example: ([x|x<-[1..],mod(7^x-1)(x^2)<1]!!) 30 -> 1140.

It's a direct implementation of the definition. It builds a list of all numbers x and picks the nth.

# Pyth, 10 bytes

e.f!%t^7Z*

A program that takes input of an integer and prints a one-indexed value.

Try it online!

How it works

e.f!%t^7Z*     Program. Input: Q
e.f!%t^7Z*ZZQ  Implicit variable fill
Implicitly print
e              the last
.f         Q  of the first Q positive integers Z
t^7Z      for which 7^Z - 1
%          mod
*ZZ   Z^2
!           is zero

# JavaScript (ES7), 40 bytes

f=(n,i=1)=>n?f(n-!((7**++i-1)%i**2),i):i

This loses precision fairly quickly due to the fact that JS loses precision by 7**19. Here's a nearly arbitrary-precision ES6 version:

f=(n,i=0)=>n?f(n-!(~-(s=++i*i,g=j=>j?g(j-1)*7%s:1)(i)%s),i):i

This finishes within about a second for test case 31.

A few longer approaches:

f=(n,i=0)=>n?f(n-!(~-(s=>g=j=>j?g(j-1)*7%s:1)(++i*i)(i)%s),i):i
f=(n,i=0)=>n?f(n-!(s=++i*i,g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(i),i):i
f=(n,i=0)=>n?f(n-!(s=>g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(++i*i)(i),i):i

# 05AB1E, 11 bytes

µ7Nm<NnÖiN¼

Try it online!

For some reason I can't get ½ to work in µ7Nm<NnÖ½N or I'd be tied with Pyth.

µ           # Loop until the counter equals n.
7Nm<       # Calc 7^x+1.
Nn     # Calc x^2.
Ö    # Check divisibility.
iN¼ # If divisible, push current x and increment counter.
# Implicit loop end.

.

• Yeah, I've had that quirk with Ö on my fix list for months but I never get around to dealing with it. Anyways, you don't need the N as µ automatically outputs the last N if the stack is empty. Commented Jan 19, 2017 at 21:34

# Python 2, 48 46 bytes

Thanks to @Dennis for -2 bytes!

f=lambda n,i=1:n and-~f(n-(~-7**i%i**2<1),i+1)

A one-indexed recursive function that takes input via argument and returns the result.

Try it online! (Recursion limit increased to allow the final test case to run)

How it works

n is the desired index, and i is the counting variable.

The expression ~-7**i%i**2<1 returns True (equivalent to 1) if i^2 divides 7^i - 1, and False (equivalent to 0) otherwise. Each time the function is called, the result of the expression is subtracted from n, decrementing n each time a hit is found; i is also incremented.

The short-circuiting behaviour of and means that when n is 0, 0 is returned; this is the base case. Once this is reached, recursion stops, and the current value of i is returned by the original function call. Rather than explicitly using i, this is done using the fact that for each function call, an increment has been performed using the -~ in front of the call; incrementing 0 i times gives i, as required.

• (~-7**i%i**2<1) saves a couple of bytes. Commented Jan 20, 2017 at 1:05
• @Dennis Of course! Thanks. Commented Jan 20, 2017 at 16:45

# Python 2, 5753 51 bytes

-4 bytes thanks to ETHproductions
-2 bytes thanks to TuukkaX

i=0
g=input()
while g:i+=1;g-=~-7**i%i**2<1
print i

Try it online!
the sequence is 1-indexed

• @ETHproductions yep c:
– Rod
Commented Jan 19, 2017 at 21:39
• Does a testcase fail if you remove the parentheses around (7**i)? I removed them and it worked for the ones I tried. Commented Jan 20, 2017 at 18:09
• @TuukkaX indeed, ** has a higher precedence than ~ and -
– Rod
Commented Jan 20, 2017 at 18:24

# Python 2, 57 bytes

This takes a really, really long time for large values. It also uses plenty of memory, because it builds the entire list way farther than necessary. The result is zero-indexed.

lambda n:[x for x in range(1,2**n+1)if(7**x-1)%x**2<1][n]

Try it online

• out of curiosity, is there any proof for the 2**n+1 as upper limit?
– Rod
Commented Jan 19, 2017 at 21:41
• @Rod Not that I know of, but considering that there are 50 values < 5000, I'm sure there's a lot more than 50 < 2**50. I could use 9**n+9, but it takes much much longer. I started running f(20) a while ago (with 2**n+1); it still hasn't completed. Commented Jan 19, 2017 at 21:44
• I don't even think there's a proof that the sequence is infinite, let alone a nice upper bound for the nth term! Commented Jan 20, 2017 at 0:24

## Mathematica, 43 bytes

I've currently got three different solutions at this byte count:

Nest[#+1//.x_/;!(x^2∣(7^x-1)):>x+1&,0,#]&
Nest[#+1//.x_/;Mod[7^x-1,x^2]>0:>x+1&,0,#]&
Nest[#+1//.x_:>x+Sign@Mod[7^x-1,x^2]&,0,#]&
• What is the character between x^2 and (7^x... in the first line? It looks like a pipe but shorter
– Sefa
Commented Jan 20, 2017 at 13:20
• @Sefa It's the Unicode character for the mathematical "divides" symbol and is used by Mathematica as an operator for Divisible. Commented Jan 20, 2017 at 13:20
• Here is one at 41 Bytes: Cases[Range[#^3],x_/;x^2∣(7^x-1)][[#]]& based on the heuristic argument that n^3 is an upper bound. I have discovered a truly marvelous proof of this, which this margin is too narrow to contain :) Commented Jan 24, 2017 at 22:46

# PARI/GP, 42 bytes

Pretty straightforward. 1-indexed, though this could easily be changed.

n->=k=1;while(n--,while((7^k++-1)%k^2,));k

or

n->=k=1;for(i=2,n,while((7^k++-1)%k^2,));k

# Python 3, 45 bytes

f=lambda n,k=2:n<2or-~f(n-(7**k%k**2==1),k+1)

Return True for input 1, which is allowed by default.

Try it online!

• I can't test this at the moment, but I assume it returns a value for other inputs? Rather than a bool? Commented Jan 20, 2017 at 11:19

# R, 35 bytes

This only works for n<=8.

z=1:20;which(!(7^z-1)%%z^2)[scan()]

However, here's a longer version which works for n<=25, for 50 bytes:

z=1:1e6;which(gmp::as.bigz(7^z-1)%%z^2==0)[scan()]
• Does this only work up to 8 because it become a long int? Commented Jan 20, 2017 at 11:20
• @george Yes, you lose accuracy as R defaults to 32 bit integers. The second version of the code uses a package, gmp, which allows arbitrarily large integers. However, I rapidly run out of RAM for computing anything above n=25. Commented Jan 20, 2017 at 13:53

# PHP, 47 49 bytes

while($n<$argv[1])$n+=(7**++$x-1)%$x**2<1;echo$x;

Only works for n<9 (7**9 is larger than PHP_INT_MAX with 64bit)

62 bytes using arbitrary length integers: (not tested; PHP on my machine doesn´t have bcmath)

for($x=$n=1;$n<$argv[1];)$n+=bcpowmod(7,++$x,$x**2)==1;echo$x;

Run with php -nr '<code>' <n>.

pseudo code

implicit: $x = 0,$n = 0
while $n < first command line argument increment$x
if equation is satisfied
increment $n print$x

## Pyke, 10 bytes

~1IX7i^tR%

Try it here!

~1         -  infinite(1)
IX7i^tR% - filter(^, not V)
7i^    -    7**i
t   -   ^-1
R% -  ^ % v
X       -   i**2
- implicit: print nth value

# Clojure, 83 bytes

(fn[n](nth(filter #(= 0(rem(-(reduce *(repeat % 7N))1)(* % %)))(iterate inc 1N))n))

Try it online!

This builds an infinite list of Java BigIntegers starting at 1 and filters them by the definition. It uses zero-based indexing to select the nth value from the filtered list.

# Perl 5, 35 Bytes

Well, this was missing, so here it is:

Try it online!