Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re^2: Numerically generate the perl sequence 1, 11, 111, ....

by TimToady (Parson)
on Oct 12, 2008 at 14:27 UTC ( #716679=note: print w/ replies, xml ) Need Help??


in reply to Re: Numerically generate the perl sequence 1, 11, 111, ....
in thread Generate the perl sequence 1, 11, 111, ....

Well, but the conversion costs something. So in Perl 6, if you're worried about efficiency, you'd probably write it like this:

1,11,111,1111 ... { $^prev * 10 + 1 }
Unless we can make the "whatever" version intuit such an algebraic relationship, in which case it would just be:
1,11,111,111 ... *
Just how far we could/should drive the intuition of the series operator is an interesting question.


Comment on Re^2: Numerically generate the perl sequence 1, 11, 111, ....
Select or Download Code
Re^3: Numerically generate the perl sequence 1, 11, 111, ....
by moritz (Cardinal) on Oct 12, 2008 at 14:48 UTC
    It shouldn't be too hard to make this work.

    By simply looking at the sequence of the pair-wise difference and ratio and correlating them to the original sequence or a constant, you can get good guesses for most commonly used sequences, if you just allow a few levels of recursion:

    1, 2, 3, 4, 5 differences 1, 1, 1, 1 # constant 1, 2, 4, 8, 16 ratios: 2, 2, 2, 2 # constant 1, 2, 3, 5, 8 differences: 1, 2, 3, 5 # sames as original shifted by one 1, 11, 111, 1111, 11111 differences: 10, 100, 1000, 10000 ratios: 10, 10, 10 # constant

    The fibonacci sequence is the only one example that needs autocorrelating. Other ones that could use the autocorrelation are -1, 1, -1, 1, ... and 0, 1, 0, 1, ....

    In case of ambiguousness the solution with the shallowest recursion would win.

    I'll try to come up with a prototype implementation that can be used as basis for a specification. But it won't be this or the next week, so have a little patience ;)

    Ideally there would be some sub or method that can be overridden to detect sequences if the built-in mechanism fails..

      One interesting and useful sequence that springs to mind is:
      2, 3, 5, 7, 11, 13, ... # Prime numbers.
      but with neither differences, nor ratios could one continue the sequence.
        ... nor can it be efficiently computed, which is why I'd leave it out.
Re^3: Numerically generate the perl sequence 1, 11, 111, ....
by JavaFan (Canon) on Oct 12, 2008 at 15:36 UTC
    Just how far we could/should drive the intuition of the series operator is an interesting question.
    It would be nice if it knew as much as the On-Line Encyclopedia of Integer Sequences in some way or another. The perl5 sources carry the Unicode database around - perhaps the perl6 source could carry the OEIS database. ;-)
      We shouldn't exaggerate.

      The Unicode database is necessary for case conversion (uc/lc) and regex matches (is something a whitespace? or a letter? or a number?). Whereas the OEIS database would be only useful for one operator, and even there it's only part of the solution - if you know that a sequence represents a part of the prime numbers, you still have no really efficient way of generating them lazily.

      However a library could easily override the infix:<...> operator and thus do what you want.

      perhaps the perl6 source could carry the OEIS database. ;-)

      I personally believe that (the smiley should suggest me that you're joking, but in case there's even the slightest attempt at being serious about this, I should point out that) a major problem with the OEIS is that it's continuously updated. So this pretty much already rules it out. Also, only a limited number of terms is recorded per sequence in the database, even taking into account ones that can be easily computed to a large extent: thus each one should be accompanied with suitable generating code too, if such code exists!

      --
      If you can't understand the incipit, then please check the IPB Campaign.
        Well, yes, I was joking. But to address your problems:
        • It being updated isn't a problem. The Unicode database gets updated as well. Just decide at some point in time before you make a release which version of the OEIS you're going to include. That's what we've been doing with the Unicode database as well. The version included in 5.10 is later than the one in 5.8.x, and the one that comes with blead perl is a later version than what's in 5.10. And perl itself gets continuously updated as well. But that doesn't stop many vendors from including perl in their distros.
        • As for your second point, many entries in the OEIS have generating formula; sometimes recursive, sometimes closed.
        Personally, I don't think the OEIS should be included just to make ".. *" smarter - but for other reasons than you point out.
Re^3: Numerically generate the perl sequence 1, 11, 111, ....
by blazar (Canon) on Oct 14, 2008 at 18:40 UTC
    Unless we can make the "whatever" version intuit such an algebraic relationship, in which case it would just be:
    1,11,111,111 ... *
    Just how far we could/should drive the intuition of the series operator is an interesting question.

    I personally believe that however appealing at first sight, it would be kinda too much! When the layman, or even the Physics doctor asks: "which is the next term after 1,1,2,3,5,8,13,21?" expecting his audience either to recocgnize the Fibonacci numbers or not to know about them, and then to blow their minds with explanations about them... the mathematician would answer: "42" In fact, given any number one can devise a rule by which the latter can be obtained from the former ones. Of course, one would want an "easy" rule. But the problem is that that "easy" is just as much as psychologically appealing as difficult to be mathematically defined.

    Thus, the question is either devoid of any sensible answer, or one should restrict himself a priori to some predefined class of rules, e.g. to linear recurrencies, and to establish an unambiguous relationship of simplicity within that class, to allow one to be picked up automatically.

    Alternatively, or better, in addition, one may allow other classes to be specified by means of a suitable adverb, e.g.

    1,11,111,1111, ... * :polyinomially

    But do we really want to make such a big subset of Perl 6 into what that seems a generic Mathematics tool?

    --
    If you can't understand the incipit, then please check the IPB Campaign.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://716679]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (11)
As of 2014-10-23 18:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (126 votes), past polls