7
\$\begingroup\$

For the purposes of this challenge, let's define a cyclic number as an integer that passes the basic part of Midy's Theorem, but not necessarily the extended theorem. This means:

the digits in the second half of the repeating decimal period are [integer is] the 9s complement of the corresponding digits in its first half

In other words, 142857 is a cyclic number because 142 + 857 = 999 and 13358664 is a cylic number because 1335 + 8664 = 9999.

The Challenge

Given an even-digit integer n > 10, determine whether n is a cyclic number by our definition. If it is, return something truthy. If it's not, return the closest cyclic number to n.

Example:

> 18
True
> 133249
132867

This is code golf, so shortest code wins.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The pseudo-cyclic number 132867 is closer to 133249 than 133866 is. Are you only considering numbers higher than the original? \$\endgroup\$
    – xnor
    Feb 27, 2015 at 10:27
  • \$\begingroup\$ @xnor No, you're right. I'll change that. \$\endgroup\$
    – aks.
    Feb 27, 2015 at 10:29
  • 2
    \$\begingroup\$ As written, " If it [cyclic], return something truthy" lets you return the number itself. Actually, the non-cyclic outputs are all truthy too. \$\endgroup\$
    – xnor
    Feb 27, 2015 at 11:01
  • \$\begingroup\$ If the first sentence of the question is taken literally, neither 142857 nor 13358664 is a cyclic number because they both "pass" the extended theorem as well as the basic one. \$\endgroup\$ Feb 27, 2015 at 12:02
  • \$\begingroup\$ @PeterTaylor the extended part is not a requirement. \$\endgroup\$
    – aks.
    Feb 27, 2015 at 18:13

7 Answers 7

1
\$\begingroup\$

Clip, 59

[vr[p[q?<a-vpa-vqp]q]}}f[d[q=qc$+n#q$dn+q$d'9]/l$d2},T*v2]n

Straightforward approach. It makes a list of all numbers, where if you the the two halves the result is all 9's, and finds which one is closest to the input. If the input is a cyclic number, it will be printed, which is allowed because all non-zero numbers are truthy.

Explanation:

[v               .- A function of v (which will be set to the input) -.
  r              .- Reduce, to find the best answer                  -.
   [p[q          .- A function of p, q                               -.
       ?         .- If                                               -.
        <        .- Compare                                          -.
         a-vp    .- the distance between one number and the input    -.
         a-vq    .- the distance between another number and the input-.
       p]q]      .- Return the closest                               -.
   }}
  f              .- Filter, to find solutions                        -.
   [d            .- A function of d (each possible value)            -.
     [q          .- Set q as... (half of length of d)                -.
       =q        .- Only if q equals...                              -.
         c       .-  the count, within...                            -.
          $      .-   the string form of...                          -.
           +     .-    the sum of...                                 -.
            n#q$d.-     the first q digits of d                      -.
            n+q$d.-     the last q digits of d                       -.
          '9     .- the digit 9                                      -.
     [/l$d2      .- half of length of d                              -.
   }
  ,T*v2          .- the numbers from 10 to double v                  -.
]n               .- With v set as the numeric value of...            -.

.-implicit-.     .- the first line of input                          -.

This passes the test-cases, though I'm not certain that the range is wide enough. If not, it can be increased by changing the *v2 to *v9 or greater.

Unfortunately, there's a bug in the interpreter's s sort-by function, so I had to use waste a few bytes using the r reduce function instead.

\$\endgroup\$
2
  • \$\begingroup\$ How can I download Clip? The esolangs page has the link password protected. \$\endgroup\$
    – Maltysen
    Feb 27, 2015 at 18:31
  • \$\begingroup\$ @Maltysen It's now unprotected. Sorry about that. \$\endgroup\$
    – Ypnypn
    Feb 27, 2015 at 18:33
1
\$\begingroup\$

Python 2, 94 characters

def r(n):
 i=0;s=1
 while 1:
    n+=i*s;M=10**(len(str(n))/2);i+=1;s=-s
    if n/M+n%M==M-1:return n

Note: the last two lines use a tab character for indentation.

Given n, this checks numbers for cyclicity in the following order: n, n-1, n+1, n-2, n+2, etc... If n is a cyclic number, it returns n (which is a truthy value). If it isn't, it returns the closest one that is.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 39

Jf!-`sjT^10/l`T2\9UyQ|}QJho%l`N2o^-QZ2J

... or

A version that might be against the rules: 33

ho%l`N2o^-QZ2f!-`sjT^10/l`T2\9UyQ

Try it online here.

The rules-breaking version just echoes the number if it is cyclic.

I believe this gives the correct output for all values, if you find something in my reasoning that is flawed, please tell me ;)

This begins by generating a list of all of the cyclic numbers from 0 to twice the input. This will obviously include each cyclic number less than the input, and includes the next cyclic number. You actually only need to add 10 ^ (digits_in_input / 2) to ensure this, but doubling takes fewer characters.

The numbers are found to be cyclic by converting them into base 10 ^ (digits_in_input / 2) and then summing the digits of this number together. All 9s are then removed from this list, and so if the list is empty the number is cyclic.

If the input is a member of this list, True is printed, otherwise the list is sorted, first by (input - value) ^ 2 and then by if the number contains an even or odd number of digits (sorting evens as less). Since pyth uses stable sorts, this is equivalent to sorting by both at once. Then the first number in this list is the nearest cyclic tag number.

This algorithm is fairly naive, but I believe it catches everything. I particularly think that the sorting could be golfed a lot.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 73

n=input()
e=10**(len(`n`)/2)-1
N=n/e+n%e*2/e;N-=N>e+1
print n==N*e or N*e

A six-digit pseudo-cyclic number like 637362 is pseudo-cyclic exactly if it's a multiple of 999, except for 999999. So, we're looking for the multiple of 999 nearest to the input n. In general, replace 999 with e, which is one less that 10**(num_digits/2).

The nearest multiple below can n be found with integer division as n/e*e. We check whether to round up with n%e*2/e, which is 1 if n%e is closer to e, and 0 if it's closer to 0. In the latter case, we add e. We also handle the 999999 case by subtract if N is too large.

Finally, before printing, we check if the original number was a multiple of e and thus already pseudo-cyclic.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I think you need to add a check that ensures e!=n. Otherwise 99, etc. return true. This also seems to happen to the algorithm that finds the next/previous value. \$\endgroup\$ Feb 27, 2015 at 15:27
  • \$\begingroup\$ @FryAmTheEggman You're right, good catch. I made a hackety fix. \$\endgroup\$
    – xnor
    Feb 28, 2015 at 4:47
  • \$\begingroup\$ Uh, the input__ surely must be input() ...? That said, everything seems ok except you sometimes get 9 as your output. i.e. for 11. \$\endgroup\$ Feb 28, 2015 at 5:19
  • \$\begingroup\$ @FryAmTheEggman Is that not the intended output? As a two-digit number, 09 is pseudo-cyclic. \$\endgroup\$
    – xnor
    Feb 28, 2015 at 5:29
  • \$\begingroup\$ I believe they have to be >10 (and must be even-digited). Sorry :( Though I could be wrong, maybe ask op? \$\endgroup\$ Feb 28, 2015 at 5:37
1
\$\begingroup\$

Ruby, 79 chars

p->n{t=n.to_s;s=t.size/2;u=t[0...s];v=t[s..-1];u.to_i+v.to_i==('9'*s).to_i}.(13358664)
\$\endgroup\$
0
\$\begingroup\$

Bash + coreutils, 118

m=$[10**(${#1}/2-1)]
jot -w%dd$1-n32Ppc $[m*9] $m$[m*9-1] $[(m*10-1)*m*10]|dc|tr -d -|sort -n|sed -n "/$1/!s/.* //p;q"

Calculates all cyclic numbers with the same number of digits as the input number, then uses sort to find the closest. In true unix fashion, nothing is printed for the "true" / "success" case, but the nearest cyclic number is printed if the input is not cyclic.

\$\endgroup\$
0
\$\begingroup\$

Python 3

209 hardcoded or 200 with user input

x = [142857, 13358664, 18, 133249]
i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    return (lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
for y in x:print((g(y)==y and True or g(y)))

Output:

True
True
True
132867

The implementation here is fairly simple. I see other entries are quite shorter; so I'm not aiming to win here, just wanted to try. This code-golfing is still very new to me.

Amendment

Having user input is simple; with one exception. For some numbers the function will throw a RuntimeError if the recursion depth hits its limit while trying to obtain a valid number counting down. That means any reasonable programmer should eat this error apporpriately and simply return False. The exception also catches any number below 27.

i=int
def g(x):
    a,b=str(x),i(len(str(x))/2)
    try:return(lambda d,c:i(d)+i(c)==10**len(d)-1 and x or g(i(d+c)-1))(a[:b],a[b:])
    except:return False
y=input();print((g(y)==y and True or g(y)))

Amendment II

Actually, now that I think of it, the user input should take less time when the output is not True:

y=input();z=g(y);print((z==y and True or z))
\$\endgroup\$
4
  • \$\begingroup\$ I like your use of recursion. Can you put it in a format that allows user input? (Don't hardcode x) \$\endgroup\$
    – aks.
    Feb 28, 2015 at 0:51
  • \$\begingroup\$ @aks like that? \$\endgroup\$
    – motoku
    Feb 28, 2015 at 1:08
  • \$\begingroup\$ Yeah, except you you change it to just input() to save a couple bytes. \$\endgroup\$
    – aks.
    Feb 28, 2015 at 1:31
  • \$\begingroup\$ @aks. there you go \$\endgroup\$
    – motoku
    Feb 28, 2015 at 1:37

Your Answer

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

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