Re: Finding the position of the number

In message <40ip72pnqb8mlvciufk57ujhm22ahv1vgr@xxxxxxx>, quasi <quasi@xxxxxxxx> writes
On Tue, 30 May 2006 23:22:39 +0100, David Hartley <me9@xxxxxxxxxxx>
wrote:

In message <ot9p729cj2s094908cqj6cu04qajj9np19@xxxxxxx>, quasi
<quasi@xxxxxxxx> writes

...

However for the _specific_ infinite string given above:

12345678910111213...

it's a reasonable to ask if there are formulas for

f(s) = the first location of a given substring s

c(s) = the canonical location of a given substring s

Thus, for example:

f(12)=2

Correction: f(12)=1

c(12)=14

If not a formula, then at least a procedure which is faster than brute
force search.

quasi

As a followup, here's a simple question ...

For the string 12345678910111213... and the functions f(s) and c(s)
specified above, characterize those substrings s for which f(s) =
c(s).

Note that c(s) is only defined if s has no leading zero digits,
whereas f(s) is defined for any digit string s.

Thus, a necessary condition for f(s) = c(s) is that s has no leading
zero digits. Clearly, this condition is not sufficient. For example

f(12) = 1 whereas c(12)=14.

There are lots of easy examples where it's obvious that f(s) = c(s).

For example, it's immediate that f(999) = c(999).

No it's not. f(999) = c(899) + 1

Ha. I missed that. You're right.

However, I think it's true (but I'm not sure) that the set of positive
integers n such that f(s) = c(s) is a set with density 1.

I haven't worked it out fully, but I think the number of k-digit numbers with this property is O(k^10). Since there are 9*10^(k-1) k-digit numbers, the proportion tends to 0 as k tends to oo.

--
David Hartley
.

Relevant Pages

  • Re: Finding the position of the number
    ... f= the first location of a given substring s ... c= the canonical location of a given substring s ... Note that cis only defined if s has no leading zero digits, ... I haven't worked it out fully, but I think the number of k-digit numbers ...
    (sci.math)
  • Re: Finding the position of the number
    ... f= the first location of a given substring s ... c= the canonical location of a given substring s ... Note that cis only defined if s has no leading zero digits, ... a necessary condition for f= cis that s has no leading ...
    (sci.math)
  • Re: Finding the position of the number
    ... In message, quasi writes ... f= the first location of a given substring s ... c= the canonical location of a given substring s ... Note that cis only defined if s has no leading zero digits, ...
    (sci.math)
  • Re: Finding the position of the number
    ... brute force search. ... Even then, assuming the substring does not exist, ... f= the first location of a given substring s ...
    (sci.math)
  • Re: Finding the position of the number
    ... Even then, assuming the substring does not exist, ... However for the _specific_ infinite string given above: ... c= the canonical location of a given substring s ...
    (sci.math)