Weekend Challenge Sharpened: Missing Positions in Champernowne's Constant

[Gerald H]

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
  ;
;

[Thomas Klemm]

(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

[Paul Dale]

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

[Gerald H]

Thomas & Paul please see clarification in edited posting #1 & yes, 690 should return 1089 (if my counting is correct).

[nlj]

(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.]

[Gerald H]

Well done, nlj!

Looks good, must subject programme to more checks.

[Gerald H]

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
  ;
;

[ttw]

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.....

[Gerald H]

Quite right, ttw, thanks for the correction.

It's the series 1, 12,123,1234..etc that's Gods' Triangle:

http://oeis.org/A007908

[nlj]

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.

[Gerald H]

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 time-flat solution (as it looks like no one else is bothered - where are the alternative solutions people!).

[Gerald H]

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!

[nlj]

(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...

[nlj]

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...

[nlj]

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...