OEIS/Negative-Positive
Clark Kimberling defined - for example - A131388 with the following rules:
Rule 1 follows. For k >= 1, let A(k) = {a(1), …, a(k)} and D(k) = {d(1), …, d(k)}. Begin with k = 1 and nonnegative integers a(1) and d(1).
Step 1: If there is an integer h such that 1 - a(k) < h < 0 and h is not in D(k) and a(k) + h is not in A(k), let d(k+1) be the greatest such h, let a(k+1) = a(k) + h, replace k by k + 1, and repeat Step 1; otherwise do Step 2.
Step 2: Let h be the least positive integer not in D(k) such that a(k) + h is not in A(k). Let a(k+1) = a(k) + h and d(k+1) = h. Replace k by k+1 and do Step 1.
Conjecture: if a(1) is an nonnegative integer and d(1) is an integer, then (a(n)) is a permutation of the nonnegative integers (if a(1) = 0) or a permutation of the positive integers (if a(1) > 0). Moreover, (d(n)) is a permutation of the integers if d(1) = 0, or of the nonzero integers if d(1) > 0.
Depending on the starting values a(1) and d(1), and with variations of the rules, there are several dozens of related sequences in the OEIS. A257705 lists 15 of them.
List of Negative-Positive sequences
The list below gives a more extended overview. The list has the following entries:
- the OEIS A-number,
- the major rule number as defined by C. Kimberling, except for "Rule 4" which he calls the "Algorithm",
- the minor rule number which gives the first constant (s = 0, 1) in Step 1 above: "... such that s - a(k) < h < 0 ...",
- a letter code for the type of the sequence:
afor a(k),dfor d(k),infor inverse(a(k)),cpfor positions of positive integers,cnfor positions of negative integers,d0for positions of non-negative terms,dnfor positions of negative terms,
- the starting values a(1) and d(1).
A131388 Rule 1.1 a 1 0 A131389 Rule 1.1 d 1 0 A131390 Rule 1.1 in 1 0 A131391 Rule 1.1 cp 1 0 A131392 Rule 1.1 cn 1 0 A131393 Rule 2.1 a 1 0 A131394 Rule 2.1 d 1 0 A131395 Rule 2.1 in 1 0 A131396 Rule 2.1 cp 1 0 A131397 Rule 2.1 cn 1 0 A175007 Rule 1.1 d0 1 0 A175008 Rule 1.1 dn 1 0 A175498 Rule 4.0 a 1 0 A175499 Rule 4.0 d 0 1 A257705 Rule 1.1 a 0 0 A257706 Rule 1.0 a 0 1 A257876 Rule 1.1 a 0 2 A257877 Rule 1.1 a 0 3 A257878 Rule 1.1 a 1 1 A257879 Rule 1.0 a 2 0 A257880 Rule 1.0 d 2 0 A257881 Rule 1.0 a 2 1 A257882 Rule 1.0 a 2 2 A257883 Rule 4.0 a 0 0 A257884 Rule 4.0 a 0 1 A257885 Rule 4.0 a 0 2 A257902 Rule 4.0 d 0 2 A257903 Rule 4.0 a 0 3 A257904 Rule 4.0 d 0 3 A257905 Rule 3.1 a 0 0 A257906 Rule 3.1 a 0 1 A257907 Rule 3.1 d 0 1 A257908 Rule 3.0 a 0 2 A257909 Rule 3.0 d 0 2 A257910 Rule 3.0 a 0 3 A257911 Rule 4.0 a 2 2 A257912 Rule 4.0 d 2 2 A257915 Rule 1.1 d 0 3 A257918 Rule 1.0 d 2 2 A257980 Rule 3.1 d 0 3 A257981 Rule 3.1 a 1 1 A257982 Rule 3.1 d 1 1 A257983 Rule 3.1 a 1 2 A257985 Rule 3.1 a 2 0 A257986 Rule 3.1 a 2 1 A257987 Rule 3.1 a 2 2 A258046 Rule 3.1 a 1 0 A258047 Rule 3.1 d 1 0
Generating Perl program
All the sequences in the list above can be generated quickly up to 100,000 terms with the following Perl program.
#!perl
# Generate OEIS Sequence A131393 and its companions
# as defined by Clark Kimberling
# @(#) $Id$
# 2018-02-24, Georg Fischer
#------------------------------------------------------
# C.f. list of sequences in https://oeis.org/search?q=A257705
# usage:
# perl negpos.pl rule s noeis n op a1 d1
# rule = 1|2|3|4
# s = 0|1
# noeis = "131388|131389|131393|131394..." (without "A")
# n = length of sequence to be generated
# op = ak, dk, cp, cn, dp(positive d(K)), dn(negative d(k)), in(inverse)
# a1 = starting value for a(1)
# d1 = starting value for d(1)
#------------------------------------------------------
# Formula (Rule 1):
# a(k) = a(k-1) + d(k)
# d(k) = max({s, s-1 ... 1-a(k-1)}) such that
# d(k) not in d(1..k-1) and
# a(k) not in a(1..k-1)
# if no such d(k) exists, then
# d(k) = min({1,2, ... a(k-1)}) such that
# d(k) not in d(1..k-1) and
# a(k) not in a(1..k-1)
# s = -1 for A131388, and s = min(-1, d(k-1)) for A131393
#--------------------------------------------------------
use strict;
my $rule = 1; if (scalar(@ARGV) > 0) { $rule = shift(@ARGV); }
my $s = 1; if (scalar(@ARGV) > 0) { $s = shift(@ARGV); }
my $noeis = ""; if (scalar(@ARGV) > 0) { $noeis = shift(@ARGV); }
my $n = 1000; if (scalar(@ARGV) > 0) { $n = shift(@ARGV); }
my $op = "ak"; if (scalar(@ARGV) > 0) { $op = shift(@ARGV); }
my $a1 = 1; if (scalar(@ARGV) > 0) { $a1 = shift(@ARGV); }
my $d1 = 0; if (scalar(@ARGV) > 0) { $d1 = shift(@ARGV); }
my $k = 1;
my $ak = $a1; my $akm1 = $ak; my %aset = ($ak, $k);
my $dk = $d1; my $dkm1 = $dk; my %dset = ($dk, $k); # $dk is h
print "# http://oeis.org/A$noeis/b$noeis.txt:"
. " table n,a(n),n=1..$n\n";
# print "# ak = $ak, dk = $dk, akm1 = $akm1, dkm1 = $dkm1 \n";
if (0) {
} elsif ($op eq "ak") {
print "$k $ak\n";
} elsif ($op eq "dk") {
print "$k $dk\n";
}
my $busy;
$k ++;
while ($k <= $n) {
$busy = 1;
if (0) {
} elsif ($rule == 1 or $rule == 2) { # for A131388, A257705 et al.
$dk = -1; # start downwards
if ($rule == 2 and $dkm1 < 0) { # for A131393 et al.
$dk = $dkm1 - 1;
}
while ($busy == 1 and $dk > $s - $akm1) { # downwards
$ak = $akm1 + $dk;
if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) {
$busy=0; $aset{$ak} = $k; $dset{$dk}=$k;
} else {
$dk --;
}
} # while downwards
if ($busy == 1) {
$dk = +1; # start upwards
}
while ($busy == 1 ) { # upwards
$ak = $akm1 + $dk;
if (!defined($aset{$ak}) and !defined($dset{$dk} )) {
$busy=0; $aset{$ak} = $k; $dset{$dk}=$k;
} else {
$dk ++;
}
} # while upwards
} elsif ($rule == 3) { # for A257905, 908
# print "$k $akm1 dk=$dkm1\n";
$dk = $s - $akm1 + 1; # start upwards in negative
while ($busy == 1 and $dk < 0) {
$ak = $akm1 + $dk;
if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) {
$busy=0; $aset{$ak} = $k; $dset{$dk}=$k;
} else {
$dk ++;
}
} # while negative
if ($busy == 1) {
$dk = +1; # start upwards
}
while ($busy == 1 ) { # upwards
$ak = $akm1 + $dk;
if (!defined($aset{$akm1 - $dk}) and !defined($dset{$dk} )) {
$busy=0; $aset{$ak } = $k; $dset{$dk}=$k;
} else {
$dk ++;
}
} # while upwards
} elsif ($rule == 4) { # "Algorithm" for A257883 et al.
$dk = $s - $ak + 1;
while ($busy == 1 ) { # upwards
$ak = $akm1 + $dk;
if (!defined($aset{$ak}) and !defined($dset{$dk} and $ak>0)) {
$busy=0; $aset{$ak} = $k; $dset{$dk}=$k;
} else {
$dk ++;
}
} # while upwards
}
if (0) {
} elsif ($op eq "ak") {
print "$k $ak\n";
} elsif ($op eq "dk") {
print "$k $dk\n";
}
# print "\t# ak = $ak, dk = $dk, akm1 = $akm1, dkm1 = $dkm1\n";
$akm1 = $ak; $dkm1 = $dk;
$k ++; # iterate
} # while $k
#--------
if ($op !~ m{ak|dk}) { # output of operations other than "ak", "dk"
my @ainv = sort(map { $_ = sprintf("%06d %d", $_, $aset{$_}); $_ } keys(%aset));
my @dpos = sort(map { $_ = sprintf("%06d %d", $dset{$_}, $_); $_ } keys(%dset));
# my $temp = shift(@dpos); # accounts for positions "-1"
# print join("\n", @dpos) . "\n";
if (0) {
} elsif ($op =~ m{in}) {
$k = 0;
$busy = 1;
while ($busy == 1 and $k < scalar(@ainv)) {
my ($j, $aj) = split(/ /, $ainv[$k]);
$j += 0; # removes the leading zeroes
$busy = ($j == $k + 1 ? 1 : 0);
if ($busy == 1) {
print "$j $aj\n";
}
$k ++;
} # while $k
} elsif ($op =~ m{cp|dp|c0|d0}) {
my $k = 0;
print join("", map { my ($j, $dj) = split(/\s+/);
$j = ($op =~ m{\Ac}) ? $j - 1 : $j + 0;
$_ = "";
if ($dj > (($op =~ m{0}) ? -1 : 0)) {
$k ++;
$_ = "$k $j\n";
}
$_ } @dpos) . "\n";
} elsif ($op =~ m{cn|dn}) {
my $k = 0;
print join("", map { my ($j, $dj) = split(/\s+/);
$j = ($op =~ m{\Ac}) ? $j - 1 : $j + 0;
$_ = "";
if ($dj < 0) {
$k ++;
$_ = "$k $j\n";
}
$_ } @dpos) . "\n";
}
} # other oper
# https://oeis.org/wiki/User:Georg_Fischer Feb. 24, 2018