[seqfan] Re: Searching OEIS question

[Frank Ruskey]

Hi Neil,
Our search criteria has some non-regular expression aspects to it, so we
ended up writing a perl script instead.  Actually, my student Sahand Saba
wrote the script.  Would you be able to run our perl script
on the database?  We didn't have anything significant to test it on, but
we think that it is correct.  Thanks!
-Frank





On 20/05/2013 2:18 PM, Neil Sloane wrote:
> Frank, I could run a grep or sed command for you on
> my private copy of the whole database, if you
> send me a command to run
>
>
> On Mon, May 20, 2013 at 4:35 PM, Frank Ruskey <ruskey at cs.uvic.ca> wrote:
>
>> I am trying to find all "nested recurrence relations" that occur in OEIS.
>> These have the form  a(n) = ....a(..... a ( ..... ) ..... )  where the
>> parens are nested as shown.
>> How to do this in a semi-intelligent fashion?  I started just trying to
>> find entries
>> that contained "a(a(".  The trouble is that the oeis seems to treat "(" as
>> a wildcard.
>> Is there some way to force it to recognize the "(" character?  Or search
>> for the
>> more general expression at the beginning of this message?  Thanks for any
>> help.
>> -Frank
>>
>> --
>> ----------------------
>> Frank Ruskey         e-mail: (last_name)(AT)cs(DOT)uvic(**DOT)ca
>> Dept. of Computer Science        fax:    250-472-5708
>> University of Victoria           office: 250-472-5794
>> Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~(last_**name)<http://www.cs.uvic.ca/~(last_name)>
>>
>>
>> --
>> This message has been scanned for viruses and
>> dangerous content by MailScanner, and is
>> believed to be clean.
>>
>>
>> ______________________________**_________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>


-- 
----------------------
Frank Ruskey         e-mail: (last_name)(AT)cs(DOT)uvic(DOT)ca
Dept. of Computer Science        fax:    250-472-5708
University of Victoria           office: 250-472-5794
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~(last_name)


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

-------------- next part --------------
#!/usr/bin/perl
use strict;
use warnings;

use Data::Dumper;

 use constant {
        STATE_READY   => 0,
        STATE_VAR   => 1,
        STATE_CALL  => 2
    };
    
while(my $string = <> ) {
	my $var = "";
	my $state = STATE_READY;
	my @chars = split("", $string);
	my $bracket_count = 0;
	my $param = "";
	for(my $i = 0; $i<scalar(@chars); $i++) {
		my $c = $chars[$i];
		#print $c;
		
		if($state == STATE_READY) {
			if($c =~ /[a-zA-Z]/) {
				$var = $c;
				$state = STATE_VAR;	
			}
		} elsif($state == STATE_VAR) {
			if($c =~ /\s/) {
				# ignore whitespace
			} elsif($c eq "(") {
				$bracket_count++;
				$state = STATE_CALL;
			} else {
				$state = STATE_READY;
			}
		} elsif($state == STATE_CALL) {
			if($c eq "(") {
				$bracket_count++;
			} elsif($c eq ")") {
				$bracket_count--;
				if($bracket_count == 0) {
					$state = STATE_READY;
					
					if($param =~ /[^a-zA-Z]$var\s*\(.*/g) {
						printf("%06d: nested call: %s(%s)\n", $., $var, $param);
					}
					
					$param = "";
					next;
				}
			}
			$param .= $c;
		}
	}
}