OEIS/Negative-Positive
Clark Kimberling defined - for example - A131388 with the following rule:
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. There are lists of related sequences in A257705, A257883 and A257905.
List of Negative-Positive sequences
The list below tries to combine the partial lists of such sequences, and to describe the variations. 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",
- a 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
The Perl program below can be used to generate all sequences of the list. It produces b-files with up to 100,000 terms rather rather quickly. The program takes parameters as described in the header. It contains the lost code portion of Rule 2 mentioned in the comment for A131393, and it implements the different variants depending on the parameter $op. The latest version of the program and its auxilliary files can be found on a Github repository.
#!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
makefile
A Unix makefile was used
- to produce the list of sequences,
- to download (once) the corresponding b-files,
- to regenerate the particular sequences and
- to compare them against the stored b-files.
#!make
# Check OEIS sequences defined by Clark Kimberling
# @(#) $Id$
# 2018-02-26: RULE=
# 2018-02-23, Georg Fischer
#
# c.f. listing.tmp (produced by target "listing", below)
#---------------------------------
TARGET=negpos
LIMIT=2000
all: rule1 rule2 rule3 rule4
#----------
# Rule 1: Step 1 downwards, Step 2 upwards
rule1: np131388 np257705 np257879 np257905
np131388: 131388
131388: 131389 175007 175008 131390 131391 131392
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0
131389:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0
175007:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=d0 A1=1 D1=0
175008:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dn A1=1 D1=0
131390:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=in A1=1 D1=0
# last 11 lines of b-file are wrong
131391:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cp A1=1 D1=0
131392:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cn A1=1 D1=0
#--------
# from A257705:
# a(1) d(1) (a(n)) (d(n))
# 0 0 A257705 A131389 except for initial terms
# 0 1 A257706 A131389 except for initial terms
# 0 2 A257876 A131389 except for initial terms
# 0 3 A257877 A257915
# 1 0 A131388 A131389
# 1 1 A257878 A131389 except for initial terms
# 2 0 A257879 A257880
# 2 1 A257881 A257880 except for initial terms
# 2 2 A257882 A257918
# Rule 1: Step 1 downwards, Step 2 upwards
np257705: 257705 257876 257877 257915 257878
257705:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0
257876:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2
257877:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3
257915:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3
257878:
make $(TARGET) RULE=1 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=1
#--------
np257879: 257706 257879 257880 257881 257882 257918
# wrong descriptions with S=1 instead of 0
257706:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1
257879:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=0
257880:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=0
257881:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=1
257882:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2
257918:
make $(TARGET) RULE=1 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=2
#----------------------------------------------------------------
rule2: np131393
# Rule 2 like Rule 1 with different start of $dk
np131393: 131393 131394 131395 131396 131397
131393:
make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0
131394:
make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0
131395:
make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=in A1=1 D1=0
# last 8 lines of b-file are wrong
131396:
make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cp A1=1 D1=0
131397:
make $(TARGET) RULE=2 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=cn A1=1 D1=0
#----------------------------------------------------------------
# Rule 3:
rule3:
# echo Rule 3
#----------------------------------------------------------------
# Rule 4: upwards from lowest
rule4: np257883
np257883: 257883 257884 257885 257903 175498 257905 175499 257908 257909 257910 257911
257883:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0
# A175499 except for first initial terms
257884: 175499
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1
175499:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=1
257885: 257902
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2
257902:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=2
257903: 257904
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3
257904:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3
175498:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0
# A175499 except for first term
257908: 257909
make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=2
257909:
make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=2
257910:
make $(TARGET) RULE=3 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=3
# A257909 except for initial terms
257911: 257912
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2
257912:
make $(TARGET) RULE=4 S=0 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=2 D1=2
# from A257883:
# a(1) d(1) (a(n)) (d(n))
# 0 0 A257883 A175499 except for initial terms
# 0 1 A257884 A175499
# 0 2 A257885 A257902
# 0 3 A257903 A257904
# 1 0 A175498 A175499 except for first term
# 1 1 A257905 A175499
# 2 0 A257908 A257909
# 2 1 A257910 A257909 except for initial terms
# 2 2 A257911 A257912
#--------
np257905: \
257905 258047 \
257906 257907 \
257908 257909 \
257910 257980 \
258046 258047 \
257981 257982 \
257983 257909 \
257985 258047 \
257986 257982 \
257987 257909
257905: 258047
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=0
258047:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=0
257906: 257907
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=0 D1=1
257907:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=1
257980:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=0 D1=3
258046: 258047
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=0
257981: 257982
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=1
257982:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=dk A1=1 D1=1
257983:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=1 D1=2
# 257909.112:
257985:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=0
# 258047
257986: 257982
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=1
# 257982.121:
257987:
make $(TARGET) RULE=3 S=1 NOEIS=$@ LEN=$(LIMIT) OPER=ak A1=2 D1=2
# 257909.122:
# from A257905:
# a(1) d(1) (a(n)) (d(n))
# 0 0 A257905 A258047
# 0 1 A257906 A257907
# 0 2 A257908 A257909
# 0 3 A257910 A257980
# 1 0 A258046 A258047
# 1 1 A257981 A257982
# 1 2 A257983 A257909
# 2 0 A257985 A257047
# 2 1 A257986 A257982
# 2 2 A257987 A257909
#---------------------------------------------------------------
negpos:
# -------------------------------------------------------
echo perl negpos.pl $(RULE) $(S) $(NOEIS) $(LEN) $(OPER) $(A1) $(D1)
test -s b$(NOEIS).txt || wget http://oeis.org/A$(NOEIS)/b$(NOEIS).txt
perl negpos.pl $(RULE) $(S) $(NOEIS) $(LEN) $(OPER) $(A1) $(D1) > A$(NOEIS).pn.tmp
grep -Ev "^ *#" b$(NOEIS).txt | head -n $(LIMIT) > bf.tmp
grep -Ev "^ *#" A$(NOEIS).pn.tmp | head -n `wc -l bf.tmp | cut -d " " -f 1` > pn.tmp
# diff -w -y --width=32 bf.tmp pn.tmp || :
diff -w -y --suppress-common-lines --width=32 bf.tmp pn.tmp || :
#--------
# chain, c.f. http://faculty.evansville.edu/ck6/integer/unsolved.html, Problem 13
chain389:
perl a1313.pl A131389 100000 > t32k.tmp
perl chain389.pl t32k.tmp
# no output => no counterexample up to 100000
chain394:
perl a1313.pl A131394 10000 > u32k.tmp
perl chain389.pl u32k.tmp
# no output => no counterexample up to 10000
block389:
perl block2.pl t32k.tmp
block394:
perl block2.pl u32k.tmp
#--------
wgetall:
wget http://oeis.org/A131388/b131388.txt
wget http://oeis.org/A131389/b131389.txt
wget http://oeis.org/A131393/b131393.txt
wget http://oeis.org/A131394/b131394.txt
#-------------------------------------------
# get the list of relevant sequence numbers
nplists: Anoeis npname npseqs
Anoeis:
grep -E "^[0-9]" makefile | sed -e "s/^/A/" \
| cut -b 1-7 | sort | uniq | tee $@.tmp
wc $@.tmp
#----
# prepare the descriptions
npname: Anoeis
grep -f Anoeis.tmp ../names | sort \
| sed -e "s/generated by/ /" -e "s/(in Comments) with//" \
-e "s/Sequence//i" \
-e "s/Conjectured permutation of the //" \
-e "s/conjectured permutation//" \
| cut -b 1-80 \
| tee $@.tmp
wc $@.tmp
#----
# compare the sequence lists to the b-files
npseqs: Anoeis wgetrest
grep -f $@.tmp ../stripped | sort | tee npseqs.tmp
perl npseqs.pl < npseqs.tmp
#----
wgetrest: Anoeis
cut -b 2-7 Anoeis.tmp > noeis.tmp
cat noeis.tmp | xargs -l -i{} make wget1 NOEIS={}
wget1:
test -s b$(NOEIS).txt || wget http://oeis.org/A$(NOEIS)/b$(NOEIS).txt
#----
listing:
make -s all TARGET=list1 | sort \
| sed -e "s/ ak / a /" -e "s/ dk / d /"\
| tee listing.tmp
wc listing.tmp
list1:
echo [https://oeis.org/A$(NOEIS) A$(NOEIS)] Rule $(RULE).$(S) $(OPER) $(A1) $(D1)
#----
# e.g. https://oeis.org/search?q=id:A257908&fmt=text
internal: Anoeis
cat Anoeis.tmp | xargs -l -i{} make intern1 ANOEIS={}
intern1:
test -s $(ANOEIS).int || \
wget -O $(ANOEIS).int "http://oeis.org/search?q=id:$(ANOEIS)\&fmt=text"
Results
The trailing terms of the 2 inverse sequences A131390 and A131395 were found to be wrong, maybe because too few terms of the normal sequence were used. For A131393 and its dependants, more terms up to 1000 were computed. All other b-files showed no differences. No differences were found either during a manual check of about 1/3 of the Mathematica programs.