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

Question

Task

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

The relevant sequence can be found here.

Rules

Shortest answer will be the winner*

Standard golfing rules apply

Loopholes are not allowed

Your answer can either be 0 or 1 indexed, please state in your answer

@nimi I wrote these down when planning and never implemented them. I've updated the question — george, 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. — briantist, 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. — mbomb007, 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. :( — briantist, Jan 19, 2017 at 21:56

nimi · Accepted Answer · 2017-01-19 20:56:55Z

7

Haskell, 34 bytes

([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.

answered Jan 19, 2017 at 20:56

nimi

35.8k4 gold badges33 silver badges96 bronze badges

Add a comment |

TheBikingViking · Accepted Answer · 2017-01-19 21:07:40Z

5

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

edited Jan 19, 2017 at 21:07

answered Jan 19, 2017 at 21:00

TheBikingViking

3,70410 silver badges22 bronze badges

Add a comment |

ETHproductions · Accepted Answer · 2017-01-20 12:49:00Z

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

Magic Octopus Urn · Accepted Answer · 2017-01-19 21:13:14Z

4

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.
            # Implicitly return top of stack (x)

.

edited Jan 19, 2017 at 21:13

answered Jan 19, 2017 at 21:08

Magic Octopus Urn

20.6k4 gold badges61 silver badges136 bronze badges

\$\begingroup\$ 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. \$\endgroup\$
– Emigna
Jan 19, 2017 at 21:34

Add a comment |

TheBikingViking · Accepted Answer · 2017-01-20 17:05:51Z

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.

\$\begingroup\$ (~-7**i%i**2<1) saves a couple of bytes. \$\endgroup\$
– Dennis
Jan 20, 2017 at 1:05 — Dennis, Jan 20, 2017 at 1:05
\$\begingroup\$ @Dennis Of course! Thanks. \$\endgroup\$
– TheBikingViking
Jan 20, 2017 at 16:45 — TheBikingViking, Jan 20, 2017 at 16:45

Rod · Accepted Answer · 2017-01-20 18:23:03Z

3

Python 2, 57 53 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

edited Jan 20, 2017 at 18:23

answered Jan 19, 2017 at 21:29

Rod

18.4k4 gold badges30 silver badges89 bronze badges

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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 19, 2017 at 21:39

mbomb007

23.3k7 gold badges60 silver badges134 bronze badges

\$\begingroup\$ out of curiosity, is there any proof for the 2**n+1 as upper limit? \$\endgroup\$
– Rod
Jan 19, 2017 at 21:41
\$\begingroup\$ @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. \$\endgroup\$
– mbomb007
Jan 19, 2017 at 21:44
\$\begingroup\$ I don't even think there's a proof that the sequence is infinite, let alone a nice upper bound for the nth term! \$\endgroup\$
– Greg Martin
Jan 20, 2017 at 0:24

Add a comment |

Martin Ender · Accepted Answer · 2017-01-20 09:58:08Z

2

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,#]&

answered Jan 20, 2017 at 9:58

Martin Ender

196k65 gold badges443 silver badges967 bronze badges

\$\begingroup\$ What is the character between x^2 and (7^x... in the first line? It looks like a pipe but shorter \$\endgroup\$
– Sefa
Jan 20, 2017 at 13:20
\$\begingroup\$ @Sefa It's the Unicode character for the mathematical "divides" symbol and is used by Mathematica as an operator for Divisible. \$\endgroup\$
– Martin Ender
Jan 20, 2017 at 13:20
\$\begingroup\$ 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 :) \$\endgroup\$
– Kelly Lowder
Jan 24, 2017 at 22:46

Add a comment |

Charles · Accepted Answer · 2017-01-20 21:04:32Z

2

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

answered Jan 20, 2017 at 21:04

Charles

2,7411 gold badge16 silver badges24 bronze badges

Add a comment |

Dennis · Accepted Answer · 2017-01-20 02:06:49Z

1

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!

answered Jan 20, 2017 at 2:06

Dennis

210k41 gold badges368 silver badges819 bronze badges

\$\begingroup\$ I can't test this at the moment, but I assume it returns a value for other inputs? Rather than a bool? \$\endgroup\$
– george
Jan 20, 2017 at 11:19

Add a comment |

rturnbull · Accepted Answer · 2017-01-20 09:50:32Z

1

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()]

answered Jan 20, 2017 at 9:50

rturnbull

3,85915 silver badges27 bronze badges

\$\begingroup\$ Does this only work up to 8 because it become a long int? \$\endgroup\$
– george
Jan 20, 2017 at 11:20
1

\$\begingroup\$ @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. \$\endgroup\$
– rturnbull
Jan 20, 2017 at 13:53

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 20, 2017 at 2:59

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 20, 2017 at 12:29

Blue

28.5k8 gold badges50 silver badges99 bronze badges

Add a comment |

miles · Accepted Answer · 2017-01-20 14:47:54Z

0

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 n^th value from the filtered list.

answered Jan 20, 2017 at 14:47

miles

16.9k2 gold badges28 silver badges94 bronze badges

Add a comment |

ChatterOne · Accepted Answer · 2017-01-20 16:25:49Z

0

Perl 5, 35 Bytes

Well, this was missing, so here it is:

map{$_ if!((7**$_-1)%($_**2))}1..<>

answered Jan 20, 2017 at 16:25

ChatterOne

1916 bronze badges

Add a comment |

Jessica · Accepted Answer · 2017-01-20 16:27:09Z

0

Powershell, too many bytes

Just to see if it was possible and it is.

[System.Linq.Enumerable]::Range(1,10000)|?{[System.Numerics.BigInteger]::Remainder([System.Numerics.BigInteger]::Pow(7,$_)-1,$_*$_) -eq 0}

answered Jan 20, 2017 at 16:27

Jessica

11 bronze badge

Add a comment |

Sean · Accepted Answer · 2017-01-20 17:18:22Z

0

Perl 6, 35 34 bytes

{grep({(7**$_-1)%%$_²},^∞)[$_]}

0-indexed.

Shaved off one byte thanks to Brad Gilbert.

edited Jan 20, 2017 at 17:18

answered Jan 19, 2017 at 21:17

Sean

7,90610 silver badges15 bronze badges

\$\begingroup\$ grep is a subroutine so you can remove the space if you put the parens after it {grep(…)} \$\endgroup\$
– Brad Gilbert b2gills
Jan 20, 2017 at 16:43

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

QBIC, 39 bytes

:{~(7^q-1)%(q^2)=0|b=b+1]~b=a|_Xq\q=q+1

I couldn't get it to run in QBasic 4.5, but it seems to run fine in QB64. For some inexplicable reason, QBasic refuses to cleanly divide 13,841,287,200 by 144, but instead gives a remainder of -128. It then returns 16 as the 7th term of this sequence instead of 12...

:{      get N from the command line, start an infinite DO-loop
~       IF
(7^q-1) Part 1 of the formula (Note that 'q' is set to 1 as QBIC starts)
%       Modulus
(q^2)   The second part
=0      has no remainder
|b=b+1  Then, register a 'hit'
]       END IF
~b=a    If we have scored N hits
|_Xq    Quit, printing the last used number (q)
\q=q+1  Else, increase q by 1. 
        [DO-loop and last IF are implicitly closed by QBIC]

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Wonder, 28 bytes

@:^#0(!>@! % - ^7#0 1^#0 2)N

Zero-indexed. Usage:

(@:^#0(!>@! % - ^7#0 1^#0 2)N)2

Filters from the list of natural numbers with a predicate that determines whether x^2 is divisible by 7^x-1, then gets the nth item in that list.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 20, 2017 at 19:41

Mama Fun Roll

9,8781 gold badge35 silver badges46 bronze badges

Add a comment |

sergiol · Accepted Answer · 2018-05-09 13:15:36Z

0

Tcl, 73 bytes

while {[incr i]} {if 0==(7**$i-1)%$i**2 {incr j;if $j==$n break}}
puts $i

Try it online!

edited May 9, 2018 at 13:15

answered Jan 21, 2017 at 15:56

sergiol

3,3981 gold badge14 silver badges31 bronze badges

Add a comment |

Stack Exchange Network

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

Task

Examples 1-index

Rules

20 Answers 20

Haskell, 34 bytes

Pyth, 10 bytes

JavaScript (ES7), 40 bytes

05AB1E, 11 bytes

Python 2, 48 46 bytes

Python 2, 57 53 51 bytes

Python 2, 57 bytes

Mathematica, 43 bytes

PARI/GP, 42 bytes

Python 3, 45 bytes

R, 35 bytes

PHP, 47 49 bytes

Pyke, 10 bytes

Clojure, 83 bytes

Perl 5, 35 Bytes

Powershell, too many bytes

Perl 6, 35 34 bytes

QBIC, 39 bytes

Wonder, 28 bytes

Tcl, 73 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
or ask your own question.

Hot Network Questions

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

Task

Examples 1-index

Rules

20 Answers 20

Haskell, 34 bytes

Pyth, 10 bytes

JavaScript (ES7), 40 bytes

05AB1E, 11 bytes

Python 2, 48 46 bytes

Python 2, 57 53 51 bytes

Python 2, 57 bytes

Mathematica, 43 bytes

PARI/GP, 42 bytes

Python 3, 45 bytes

R, 35 bytes

PHP, 47 49 bytes

Pyke, 10 bytes

Clojure, 83 bytes

Perl 5, 35 Bytes

Powershell, too many bytes

Perl 6, 35 34 bytes

QBIC, 39 bytes

Wonder, 28 bytes

Tcl, 73 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathsequence or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
or ask your own question.