31
\$\begingroup\$

This challenge is a tribute to our Legendary Challenge Writer™, Calvin's Hobbies — now renamed to Helka Homba —, in the same spirit as Generate Dennis Numbers.

Calvin is a pretty impressive contributor to PPCG, with the 6th most reputation overall and probably indisputibly the best challenge writing skills out of all of us. However, of course, for this challenge, we will focus on his user ID.

26997 might not look very interesting at first. In fact, it's almost interesting in a few ways. For example, here's a chart of 26997 mod <n> for certain values of n:

n | 26997 % n ----+----------- 3 | 0 4 | 1 5 | 2 6 | 3 7 | 5 :( 8 | 5 9 | 6 10 | 7 

However, 26997 is one of the few numbers that can be represented by (n * 10)n - n, where n is an integer > 0.

Here are the first few numbers which can be expressed in this way, which we will henceforth call Calvin Numbers:

9 398 26997 2559996 312499995 46655999994 8235429999993 1677721599999992 387420488999999991 99999999999999999990 28531167061099999999989 8916100448255999999999988 3028751065922529999999999987 1111200682555801599999999999986 437893890380859374999999999999985 184467440737095516159999999999999984 82724026188633676417699999999999999983 39346408075296537575423999999999999999982 19784196556603135891239789999999999999999981 10485759999999999999999999999999999999999999980 

These Calvin Numbers have some interesting properties. More patterns emerge when we right-align them and highlight all the 9s:

screenshot

The ones that we're interested in for this challenge are:

  • Regardless of n, every Calvin Number ends with 10n - n.

    So, Calvin(1) ends with 9, Calvin(2) ends with 98, and the pattern continues 997, 9996, 99995, etc., with each successive Calvin Number counting down and adding an extra 9 to the beginning.

  • For values of n where n % 10 == 0 (i.e. n is divisble by 10), Calvin(n) ends with 102n - n.

    That is, the pattern extends for twice as many digits as normal, with an extra number of 9s at the beginning equal to n.

  • When n is a power of 10 (10, 100, 1000, etc.), the pattern extends even further—every single digit is either a 9 or a 0.

    This pattern is the following: (n + 1) * 10n - n nines, and n zeroes. This is easier to understand in a chart (your solution will only have to handle numbers up to 10000 anyway, so this is all you need):

    n | Calvin(n) -------+----------------------- 10 | 19 nines, 1 zero 100 | 298 nines, 2 zeroes 1000 | 3997 nines, 3 zeroes 10000 | 49998 nines, 4 zeroes 

    The number of nines even exhibits several properties of Calvin Numbers itself, but that's too much detail for this challenge.

Challenge

Calvin Numbers get far too big, far too quickly, for a "get the nth Calvin Number challenge to be feasible in languages without arbitrary-precision integers. Therefore, the challenge is to determine whether a number fits the above patterns—that is, whether a number is a "candidate Calvin Number" or not.

Here are the criteria for a number to be considered a candidate Calvin Number (hereafter referred to as a CCN for short):

  • It ends with a number that fits the pattern 10n - n for an integer n.

    So, to be a CCN, a number must end with 9, or 98, or 997, 9996, 99995, etc.

  • If the last digit is 0, it must also end with 102n - n, for the same n as in the previous point.

    This means that 12312312399999999999999999999999999999999999980 is not a CCN, but 10485759999999999999999999999999999999999999980 is (it's the correct one, in fact).

  • If the value of n in the previous two steps is a power of 10, the entire number must fit the third pattern described above.

Input / Output

The input will be provided as a string, and it will always represent a number that is less than Calvin(10000) + 10000 (which can also be expressed as 1050000). (To clarify, the greatest possible input is 50000 nines, and the least possible input is 1.)

The output should be a truthy value if the input represents a number which is a CCN, and a falsy value otherwise. For the definitions of these terms, see meta.

Test cases

Inputs that should result in a truthy value:

9 26997 99999999999999999990 437893890380859374999999999999985 10485759999999999999999999999999999999999999980 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900 259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999850 1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999028 

Inputs that should result in a falsy value:

1 26897 79999999999999999990 437893890380859374299999999999985 12312312399999999999999999999999999999999999980 999998999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900 259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911111 1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999027 

Rules

  • You may not, at any point in your program, handle integers larger than 18446744073709551615 (264), if your language has support for arbitrary-precision integers (or number types with a high enough precision to allow storing numbers greater than this).

    This is simply to prevent solutions that loop through all possible Calvin Numbers (or all possible values of 10n - n).

  • This is , so the shortest code in bytes will win.

\$\endgroup\$
7
  • \$\begingroup\$ "If the value of n in the previous two steps is a power of 10, the entire number must fit the third pattern described above." What does the 'third pattern' refer to? \$\endgroup\$ Commented Sep 14, 2015 at 0:53
  • \$\begingroup\$ @feersum There's a bulleted list of three things—it's the last one. \$\endgroup\$ Commented Sep 14, 2015 at 1:16
  • \$\begingroup\$ I don't understand why the second-to-last falsy test-case is falsy. What rule does it violate? \$\endgroup\$ Commented Sep 14, 2015 at 4:51
  • \$\begingroup\$ @AlexisKing Good catch; anything that ends in 9 should be truthy. Fixed. \$\endgroup\$ Commented Sep 14, 2015 at 10:56
  • \$\begingroup\$ @Doorknob Even with that change, the number still seems to fit the criteria. Shouldn't a number ending in 845 have 152 nines? It seems to have more than enough. Were there supposed to be half the number? \$\endgroup\$ Commented Sep 14, 2015 at 20:45

1 Answer 1

10
\$\begingroup\$

Racket, 353

(require srfi/13)(let([s(~a(read))])(for/or([n(range 1 999)])(and(let*([y(string-length(~a n))])(string-suffix?(string-append(make-string(-(if(=(modulo n 10)0)(* 2 n)n)y)#\9)(~r #:min-width y #:pad-string"0"(-(expt 10 y)n)))s))(let([n(inexact->exact(/(log n)(log 10)))])(or(not(integer? n))(string-prefix?(make-string(-(*(+ 1 n)(expt 10 n))n)#\9)s)))))) 

Accepts a number from stdin, outputs #t or #f.

Ungolfed version:

(require srfi/13) (define (calvin? str) (for/or ([n (in-range 1 10001)]) (and (10^n-n$? n str) (or (not (integer? (/ (log n) (log 10)))) (expt-of-ten-check? n str))))) (define (10^n-n$? n str) (let* ([div-by-ten? (zero? (modulo n 10))] [digits (string-length (~a n))] [nines (- (if div-by-ten? (* 2 n) n) digits)] [suffix (string-append (make-string nines #\9) (~r #:min-width digits #:pad-string "0" (- (expt 10 digits) n)))]) (string-suffix? suffix str))) (define (expt-of-ten-check? n str) (let* ([n (inexact->exact (/ (log n) (log 10)))] [nines (- (* (add1 n) (expt 10 n)) n)] [prefix (make-string nines #\9)]) (string-prefix? prefix str))) 

I normally don't do code golf, and Racket certainly isn't the most suitable language for it, but nobody had answered yet, so I figured I'd give it a shot. ;)

\$\endgroup\$
1
  • \$\begingroup\$ They might've been waiting for me to answer, but given my post history it's probably best that you didn't wait around ;) \$\endgroup\$ Commented Sep 15, 2015 at 21:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.