You are given a nonary (base 9) non-negative integer consisting of the digits 0 through 8 as usual. However the number of digits in this number (with no leading zeros) is a prefect square.

Because of this, the number can be arranged in a square grid (with the reading order still preserved).

Example with 1480 (1125 base 10):


Now let every digit in such a nonary grid indicate a motion to another grid space (with periodic boundary conditions):


This is saying that

0 = stay still
1 = move right
2 = move right and up
3 = move up
8 = move right and down

So, if in the 1480 grid you start at the 4, you then move up (remember pbc) and left to the 8, which means you move right and down back to the 4, starting a cycle with period 2.

In general this process is continued until you get to a 0 or a cycle is noticed. (A 0 is considered a cycle with period 1.)

In the case of 1480, the period eventually reached at each of the 4 starting digits is 2 2 2 1 respectively.

For a larger grid these numbers might be larger than 8, but we can still use them as "digits" in a new nonary number (simply the coefficients of 9^n as if they were digits):

2*9^3 + 2*9^2 + 2*9 + 1 = 1639 (base 10) = 2221 (base 9)

We will call this the strength of the original nonary number. So the strength of 1480 is 1639 (base 10) or, equivalently, 2221 (base 9).


Write the shortest program that tells whether the strength of a nonary number is greater than, less than, or equal to the nonary number itself. (You do not necessarily need to compute the strength.)

The input will be a non-negative nonary number that contains a square number of digits (and no leading zeros besides the special case of 0 itself). It should come from the command line or stdin.

The output should go to stdout as:

G if the strength is larger than the original number (example: 1480 -> strength = 2221)
E if the strength is equal to the original number (example: 1 -> strength = 1)
L if the strength is less than the original number (example: 5 -> strength = 1)

Fun Bonus Challenge:
Whats the highest input you can find that is equal to its strength? (Is there a limit?)

  • \$\begingroup\$ As for the input, is it given as a decimal number the digits of which are the same as the nonary number or as the decimal (or binary) representation of the nonary number? i.e: for 1480(non) will the input be 1480 or 1125? \$\endgroup\$
    – overactor
    Commented Aug 26, 2014 at 10:31
  • \$\begingroup\$ @overactor In nonary format. \$\endgroup\$
    – user31074
    Commented Aug 26, 2014 at 10:37
  • 2
    \$\begingroup\$ I'm fairly confident that no-one will find a higher input that equals its strength than 10^71-1(non) that is, a 64 digit number that consists only of 8's \$\endgroup\$
    – overactor
    Commented Aug 26, 2014 at 10:53
  • \$\begingroup\$ @overactor It might be possible with cycles of period greater than 8, I think. \$\endgroup\$ Commented Aug 26, 2014 at 17:22
  • \$\begingroup\$ @MartinBüttner i will be thoroughly impressed if you find any of those. \$\endgroup\$
    – overactor
    Commented Aug 26, 2014 at 17:51

4 Answers 4


Python 2, 213 209 202

Edit: Removed shortcircuiting, which is sometimes incorrect. See below.

(Largely) The same algorithm as @KSab, but very heavily golfed.

for i in range(s*s):
 while(i in a)<1:a+=[i];x='432501678'.find(n[i]);i=(i+x%3-1)%s+((i/s+x/3-1)%s)*s


  • 213: Short-circuiting, flawed solution.

  • 209: First working solution.

  • 202: Combined the two string lookups into one.

Edit: I just realised that this program, and thus KSab's too, were flawed in that they ignore multidigit cycle lengths. Example failure:


While the 3 has a cycle length of 2, and thus the above algorithm short circuits to 'L', this should in fact return 'G', because the cycle length of 14 on the second digit more than overcomes that. I have therefore changed the program. It also got shorter, funnily enough. To test your program, use 3117275531177455. It should return G.

  • \$\begingroup\$ Wow I thought I golfed it down a fair bit but you did some pretty clever stuff there. \$\endgroup\$
    – KSab
    Commented Aug 27, 2014 at 3:27
  • \$\begingroup\$ @KSab Thanks - your algorithm was very clever to start with - I couldn't find any better way to do it. \$\endgroup\$
    – isaacg
    Commented Aug 27, 2014 at 5:19

Python 296

Not actually too inefficient, it only checks as many digits as it needs to.

for i in range(s**2):
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s

As for numbers equal to their strength, I think the only solutions are, for every N x N square up to N=8 a square containing N in every space. My thinking is that since every number in a loop must be the same number (the length of the loop) each loop would have to be all in one direction. This of course means that the loop's size must be N (and each element must be N). I'm pretty sure that this logic can be applied to squares and loops of any size, meaning there are no squares equal to their strength other than the first 8.

  • \$\begingroup\$ Though unlikely, it might be possible for loops larger than 8. \$\endgroup\$
    – overactor
    Commented Aug 27, 2014 at 6:14
  • 2
    \$\begingroup\$ I think this gives the wrong result on 3117275531177455, because of loop sizes greater than 8. See my post. \$\endgroup\$
    – isaacg
    Commented Aug 27, 2014 at 6:51
  • 1
    \$\begingroup\$ @isaacg Oh I didn't see that, I changed it to make it work but I'm not going to try and golf it further because that would pretty much be just copy-pasting your answer. Oh and I think you can improve your last two lines by using cmp. \$\endgroup\$
    – KSab
    Commented Aug 27, 2014 at 18:38

CJam - 81


Try it at http://cjam.aditsu.net/

It can probably be golfed some more.


Lua - Not golfed yet

Just putting in here for safekeeping. I'll golf it (and implement the "For a larger grid these numbers might be larger than 8, but we can still use them as "digits"") later. Works though.


    for y=1,q do
    for x =1,q do
for y=1,q do
    for x=1,q do
        cx=x cy=y pxy=''sd=0
        while pxy:match(cx..':%d*:'..cy..' ')==nil do
            pxy=pxy..cx..':'..sd..':'..cy.." "
            cx=ccx cy=ccy
            if cx<1 then cx=q elseif cx>q then cx=1 end
            if cy<1 then cy=q elseif cy>q then cy=1 end
nn=tonumber(n,9) tn=tonumber(ssd,9)
if tn>nn then print("G") elseif tn==nn then print("E") else print("L") end

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.