Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant

07302015, 04:53 PM
(This post was last modified: 08082015 05:14 AM by Gerald H.)
Post: #1




Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
Every natural number appears at some position in the concatenation of the natural numbers  sometimes called The Gods' Triangle, but let us call it N:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500.... For example 399 starts at the 1087th digit of N & 400 at the 1090th digit, counting from the first 1 rightwards. The programme for the 49G below gives the starting position in N for the entry integer. Challenge You will notice that for consecutive integers, eg 399 & 400, the positions are not consecutive, so 1088 & 1089 do not appear as the starting positions of any integer. Write a programme that on input of the index of a number, say C, that cannot appear as position of any integer returns C, eg for index 1 the programme returns 11 as 11 is the lowest number not representing the start position of an integer. Clarification following posts #2 & #3 For input 2 the programme should return 13 for 3, 15........ Sorry for the imprecision of definition. Code:


07302015, 06:52 PM
(This post was last modified: 07302015 07:01 PM by Thomas Klemm.)
Post: #2




RE: Weekend Challenge: Missing Positions in Gods' Triangle
(07302015 04:53 PM)Gerald H Wrote: Write a programme that on input of the index of a number, say C, that cannot appear as position of any integer returns C Just to make sure I understand you correctly: For input 690 the program should return 1089. Because 1089 is the 690th number in the list of positions that do not appear as the starting position of any integer in God's Triangle. Kind regards Thomas 

07302015, 10:18 PM
Post: #3




RE: Weekend Challenge: Missing Positions in Gods' Triangle
Might it be more interesting to allow numbers to be found earlier?
Your example of position 1088 would then be the start of a new and previous unseen integer: 994. I'd probably stipulate that the search must stop when the shortest new integer is found and that only one integer can begin at any position. Under these conditions C(1) is still 11. But C(2) is not 13, since 112 is there. C(2) is 31. Pauli 

07312015, 05:23 AM
(This post was last modified: 07312015 05:47 AM by Gerald H.)
Post: #4




RE: Weekend Challenge: Missing Positions in Gods' Triangle
Thomas & Paul please see clarification in edited posting #1 & yes, 690 should return 1089 (if my counting is correct).


08042015, 05:04 AM
Post: #5




RE: Weekend Challenge: Missing Positions in Gods' Triangle
(07302015 04:53 PM)Gerald H Wrote: Write a programme that on input of the index of a number, say C, that cannot appear as position of any integer returns C, eg The following does the trick: Code: « As requested, it returns 11 for an input of 1, 1089 for an input of 690, and, for example, 1124999998 for an input of 987654321. [Here i refers to an index into God's Number, c refers to the "dead" digits of God's Number where no integer starts, and ch (characteristic) is the power of ten currently being addressed as we iterate from the "units" to the "tens" to the "hundreds" etc.. All local variables are initialised to zero except for the input value, c.] 

08042015, 07:23 AM
Post: #6




RE: Weekend Challenge: Missing Positions in Gods' Triangle
Well done, nlj!
Looks good, must subject programme to more checks. 

08072015, 05:08 PM
Post: #7




RE: Weekend Challenge: Missing Positions in Gods' Triangle
While nlj's programme is a complete solution of the problem it is not really what I wanted.
The sharpened problem is to present a programme giving the same results without iterations, recursions, loop etc. Meanwhile here's a slightly more readable version of nlj's programme: Code:


08082015, 03:53 AM
Post: #8




RE: Weekend Challenge Sharpened: Missing Positions in Gods' Triangle
This number is called "Champernowne's Number" after the guy who proved that it was a normal number. A normal number has the proper frequency of digits. Almost all numbers are normal, but few are known to be so. All the known ones are made by concatenation of various things. An absolutely normal number has the proper frequency of single digits, double digits, etc. The number in the OP has this property.
1,2,3,4,5,6,7,8,9,10,11,12..... is the construction. It's also possible in base 2: 0,1,10,11,100,101.... or 011011100101..... 

08082015, 05:08 AM
(This post was last modified: 08082015 05:26 AM by Gerald H.)
Post: #9




RE: Weekend Challenge Sharpened: Missing Positions in Gods' Triangle
Quite right, ttw, thanks for the correction.
It's the series 1, 12,123,1234..etc that's Gods' Triangle: http://oeis.org/A007908 

08082015, 02:26 PM
Post: #10




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
Hi Gerald,
I'm still puzzling away at this now "week and two weekend" challenge. I have three questions for clarification: 1. Is this a programming challenge or a mathematical challenge? If the solution requires work like Champernowne's proof, then it's a long way beyond the reach of my efforts! (And I suspect Champernowne didn't come up with it in a weekend!) 2. In your initial post you provided code for finding i(n), the index (into Champernowne's Number) of the start of a given integer n. Are you anticipating that the solution to the challenge will need to call this code? 3. When you request a solution "without iterations, recursions, loop etc.", am I correct in assuming that you include the summation function Σ in your "etc."? In my efforts to eliminate iteration, I've been trying to use the formula for the sum of an arithmeticogeometric sequence. It looks promising but I'm stuck with needing to solve m * 10^m = n (where m and n are positive integers). It's easy for a human to solve by inspection for any given n, but so far I'm puzzled to see how to solve it on the calculator without iterating in some way. 

08082015, 03:25 PM
Post: #11




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
Welcome back, nlj.
I'll do my best to answer your points: 1 Both. You have to deal with the necessary maths to know what to programme  You don't have to consider the proof that the number is normal. 2 My programme is the type of programme I really want, in principle the time taken is the same as the time needed for the powering operation. 3 Summation would be exclude but powering is OK, so is multiplication. I'm a bit primitive, & although multiplication is iterated addition & powering iterated multiplication I'd allow them, I guess basically through habituation & speed. I don't have a better answer than yours but you have displayed the best understanding of the problem & may have the best chance of finding a more timeflat solution (as it looks like no one else is bothered  where are the alternative solutions people!). 

08082015, 04:27 PM
Post: #12




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
So, nlj, you have woken me up & I'm having to think again.
Please check what your programme returns for input 91  I get 190, where I believe 100 starts! 

08082015, 06:01 PM
Post: #13




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant  
08092015, 10:12 PM
Post: #14




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
As far as fixing my bug goes, if I replace the final two lines of my code in Post #5:
Code: c.to.go c.width.at.ch MOD with: Code: + then the bug is removed (and the program is hideous) and correctly the program returns 11 for an input of 1, 191 for an iinput of 91, 1089 for an input of 690, and, for example, 1124999999 for an input of 987654321. I have a version with no iteration under construction... 

08102015, 02:54 AM
Post: #15




RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
The following is weird (and wonderful):
Code: ch min_c max_c i(max_c) Where I break Champernowne's Number into "levels", where ch is the characteristic of the logarithm of the integers at a given level (i.e. integers 1 to 9 at the level with ch = 0; 10 to 99 for ch = 1 etc.) and min_c is the number of the smallest "missing position" at that level, max_c is the largest "missing position" at that level and i(max_c) is the index into Champernowne's Number of max_c. I believe this observation will permit me to eliminate iteration from my solution. But I'm still working on that bit... 

« Next Oldest  Next Newest »

User(s) browsing this thread: 4 Guest(s)