[seqfan] Re: 3-sequences relations using Robert Gerbicz's seeker.c

[Robert Gerbicz]

2010/8/23 Georgi Guninski <guninski at guninski.com>

> using Robert Gerbicz's seeker.c [1] [2] (modified for speed version) i
> looked for inter-oeis relations involving 3 sequences. results:
>
> in about 90 minutes, about 50 000 sequence analyzed on a singe core:
>
> 167284 relations found (sic, false positives)
>
> the first 30 terms of pruned "stripped" file were used, a lot of false
> positives due to insufficient number of terms.
>
> the database in oeis format is at:
> http://stefan.guninski.com/seq/seekjn1
>
> searchable web interface:
> http://stefan.guninski.com/cgi/oeis-seekjn1.cgi?q=%25F
>
> (use +Anumber to search for a sequence)
>
> search for the primes:
> http://stefan.guninski.com/cgi/oeis-seekjn1.cgi?q=%2BA000040
>
> search for euler_phi:
> http://stefan.guninski.com/cgi/oeis-seekjn1.cgi?q=%2BA000010
>
> some random results (might be wrong):
>
> %F A108954 =A000010-A077150
> %F A000040 =A090417-A031165
>
> [1] http://list.seqfan.eu/pipermail/seqfan/2010-August/005615.html
> [2] http://list.seqfan.eu/pipermail/seqfan/2010-August/005617.html
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

It would be possible to generate (or only count) all 4-sequences relations
in about the same amount of time (by a new code), unfortunately to do this
in Ram is impossible, but by using harddisk is possible. So to find all s1
op1 s2 op2 s3 op3 s4 = 0 relation (where op={+,-,*,/}), for example:
s1-s2*s3*s4=0 or s1*s2/s3-s4=0.

The idea is the same s1 OP1 s2 = s3 OP2 s4, generate both sides then do a
binary search.

"A108954 =A000010-A077150"

It is actually true, proof: eulerphi(n)=#{m: 1<=m<=n and gcd(n,m)=1}=#{m:
n+1<=m<=2n and gcd(n,m)=1} because if m=n+i then gcd(n+i,n)=gcd(i,n). But in
A077150 we take only m values that is composite. So for the remaining
numbers: if m is prime then gcd(n,m)=1, since m>n and m is prime, and there
are primepi(2n)-primepi(n) prime numbers in (n,2n] interval. So
A108954+A077150=A000010 what is needed.