Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
07-30-2015, 04:53 PM (This post was last modified: 08-08-2015 05:14 AM by Gerald H.)
Post: #1
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
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:

12345678910111213141516171819202122232425262728293031323334353637383940414243444​54647484950515253545556575859606162636465666768697071727374757677787980818283848​58687888990919293949596979899100101102103104105106107108109110111112113114115116​11711811912012112212312412512612712812913013113213313413513613713813914014114214​31441451461471481491501511521531541551561571581591601611621631641651661671681691​70171172173174175176177178179180181182183184185186187188189190191192193194195196​19719819920020120220320420520620720820921021121221321421521621721821922022122222​32242252262272282292302312322332342352362372382392402412422432442452462472482492​50251252253254255256257258259260261262263264265266267268269270271272273274275276​27727827928028128228328428528628728828929029129229329429529629729829930030130230​33043053063073083093103113123133143153163173183193203213223233243253263273283293​30331332333334335336337338339340341342343344345346347348349350351352353354355356​35735835936036136236336436536636736836937037137237337437537637737837938038138238​33843853863873883893903913923933943953963973983994004014024034044054064074084094​10411412413414415416417418419420421422423424425426427428429430431432433434435436​43743843944044144244344444544644744844945045145245345445545645745845946046146246​34644654664674684694704714724734744754764774784794804814824834844854864874884894​90491492493494495496497498499500....

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:
 If you don'like CODE .... replace it with xSIZE COERCE. ::   CK1&Dispatch   # FF   ::     FPTR2 ^ZABS     DUP     CODE 00025 143174E78FB9760131174143818F858DC7530     DUPUNROT     FPTR2 ^#>Z     FPTR2 ^RMULText     Z1_     FPTR2 ^RADDext     Z10_     ROT     FPTR2 ^PPow#     Z1_     FPTR2 ^RSUBext     Z9_     FPTR2 ^ZQUOText     FPTR2 ^RSUBext   ; ;
07-30-2015, 06:52 PM (This post was last modified: 07-30-2015 07:01 PM by Thomas Klemm.)
Post: #2
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Weekend Challenge: Missing Positions in Gods' Triangle
(07-30-2015 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
07-30-2015, 10:18 PM
Post: #3
 Paul Dale Senior Member Posts: 1,770 Joined: Dec 2013
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
07-31-2015, 05:23 AM (This post was last modified: 07-31-2015 05:47 AM by Gerald H.)
Post: #4
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
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).
08-04-2015, 05:04 AM
Post: #5
 nlj Junior Member Posts: 32 Joined: Apr 2015
RE: Weekend Challenge: Missing Positions in Gods' Triangle
(07-30-2015 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

for index

1

the programme returns

11

as 11 is the lowest number not representing the start position of an integer.

The following does the trick:

Code:
«   0 9 NDUPN DROP   → c      Σi Σc ch     num.ints.at.ch int.width.at.ch     c.width.at.ch tot.c.width.at.ch      c.to.go ints.to.go   «     1 CF     WHILE 1 FC? REPEAT       ch ALOG 9 * 'num.ints.at.ch' STO       ch 1 + 'int.width.at.ch' STO       ch 'c.width.at.ch' STO       num.ints.at.ch c.width.at.ch * 'tot.c.width.at.ch' STO       IF Σc tot.c.width.at.ch + c ≥ THEN         1 SF       ELSE         tot.c.width.at.ch 'Σc' STO+         num.ints.at.ch int.width.at.ch * 'Σi' STO+       END       1 'ch' STO+        END     c Σc - 'c.to.go' STO     c.to.go c.width.at.ch / FLOOR 'ints.to.go' STO     Σi     ints.to.go int.width.at.ch *     c.to.go c.width.at.ch MOD     + +   » »

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.]
08-04-2015, 07:23 AM
Post: #6
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
RE: Weekend Challenge: Missing Positions in Gods' Triangle
Well done, nlj!

Looks good, must subject programme to more checks.
08-07-2015, 05:08 PM
Post: #7
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
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:
 ::   CK1&Dispatch   # FF   ::     Z0_     BINT9     NDUPN     DROP'     NULLLAM     BINT10     NDUPN     DOBIND     FALSE     BEGIN     7GETLAM     Z10_     OVER     FPTR2 ^Z2BIN     FPTR2 ^RP#     Z9_     FPTR2 ^RMULText     6PUTLAM     DUP     Z1_     FPTR2 ^RADDext     5PUTLAM     DUP4PUTLAM     6GETLAM     FPTR2 ^RMULText     DUP     3PUTLAM     8GETLAM     FPTR2 ^RADDext     10GETLAM     Z>=     ::       casedrptru       3GETLAM       8GETLAM       FPTR2 ^RADDext       8PUTLAM       6GETLAM       5GETLAM       FPTR2 ^RMULText       9GETLAM       FPTR2 ^RADDext       9PUTLAM     ;     Z1_     7GETLAM     FPTR2 ^RADDext     7PUTLAM     DUP     UNTIL     DROP     9GETLAM     10GETLAM     8GETLAM     FPTR2 ^RSUBext     4GETLAM     FPTR2 ^ZDIVext     SWAP     5GETLAM     ABND     FPTR2 ^RMULText     FPTR2 ^RADDext     FPTR2 ^RADDext   ; ;
08-08-2015, 03:53 AM
Post: #8
 ttw Member Posts: 262 Joined: Jun 2014
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.....
08-08-2015, 05:08 AM (This post was last modified: 08-08-2015 05:26 AM by Gerald H.)
Post: #9
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
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
08-08-2015, 02:26 PM
Post: #10
 nlj Junior Member Posts: 32 Joined: Apr 2015
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.
08-08-2015, 03:25 PM
Post: #11
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
Welcome back, nlj.

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 time-flat solution (as it looks like no one else is bothered - where are the alternative solutions people!).
08-08-2015, 04:27 PM
Post: #12
 Gerald H Senior Member Posts: 1,573 Joined: May 2014
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!
08-08-2015, 06:01 PM
Post: #13
 nlj Junior Member Posts: 32 Joined: Apr 2015
RE: Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant
(08-08-2015 04:27 PM)Gerald H Wrote:  Please check what your programme returns for input 91 - I get 190, where I believe 100 starts!
Yes, I have the same error (and I suspect that 1089 for an input of 690 is also off). Fixing that...
08-09-2015, 10:12 PM
Post: #14
 nlj Junior Member Posts: 32 Joined: Apr 2015
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:
    +     c.to.go     ints.to.go c.width.ch *     -     DUP     IF 0 ≠     THEN 1 + +     ELSE DROP     END

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...
08-10-2015, 02:54 AM
Post: #15
 nlj Junior Member Posts: 32 Joined: Apr 2015
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) 0   0       0        (9) 1   1       90       189 2   91      1890     2889 3   1891    28890    38889 4   28891   388890   488889 5   388891  4888890  5888889 ... 13  118888888888891  1288888888888890  1388888888888889 ...

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: 1 Guest(s)