Re: Finding the position of the number

On Tue, 30 May 2006 16:03:19 -0400, quasi <quasi@xxxxxxxx> wrote:

On 30 May 2006 12:44:08 -0700, "Pubkeybreaker"
<Robert_silverman@xxxxxxxxxxxx> wrote:


Atrus wrote:
Is there any formula that I could use that would find the position of a
number in a large sequence of numbers.

For example to find ' 11 ' in the string of numbers 1234567891011, some
formula would return the number 12, does anyone know of a formula that
would do this?

Thanks!

This has got to rank as one of the most clueless questions I've
ever seen within this newgroup. And I've been reading it for over
20 years.

Of course there's no method that would work in general, except for
brute force search. Even then, assuming the substring does not exist,
how would you know when to stop?

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

If the set of positive integers n for which for which f(s) = c(s) is
not easily characterized (where s is the string form of n), then can
we at least determine the density of the set?

quasi
.

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, ... a necessary condition for f= cis that s has no leading ...
    (sci.math)
  • Re: [QUIZ] Longest Repeated Substring (#153)
    ... My hack at the substring problem is based on suffix ... in the original string. ... def initialize ...
    (comp.lang.ruby)
  • Favicon type detection - possible?
    ... this is my cobbled together browser detection ... {string: navigator.userAgent, ... subString: "OmniWeb", ... {// for newer Netscapes ...
    (comp.lang.javascript)
  • Comments on Comments (was Re: Getting to 100 (#119))
    ... # yield each partitioning of the receiver into count partitions ... # an initial substring of increasing length, ... # the string into count-1 partitions. ... #:ops - an array of strings representing the operators to be inserted into ...
    (comp.lang.ruby)
  • Re: Computability and logic
    ... as regards a mathematical formulation of a substring ... substring in a string with another substring? ... result of substituting a term for a variable in a formula'. ... As I recall, he doesn't get into replacing term for term, ...
    (sci.logic)