#!/usr/bin/perl -w
# Copyright 2012, 2013 Kevin Ryde
# This file is part of Math-PlanePath.
#
# Math-PlanePath is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-PlanePath is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
use 5.004;
use strict;
use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099
use Test;
plan tests => 13;
use lib 't','xt';
use MyTestHelpers;
BEGIN { MyTestHelpers::nowarnings(); }
use MyOEIS;
use Math::PlanePath::Base::Digits
'digit_split_lowtohigh',
'digit_join_lowtohigh';
use Math::PlanePath::GrayCode;
use Math::PlanePath::Diagonals;
# uncomment this to run the ### lines
#use Smart::Comments '###';
sub numeq_array {
my ($a1, $a2) = @_;
if (! ref $a1 || ! ref $a2) {
return 0;
}
my $i = 0;
while ($i < @$a1 && $i < @$a2) {
if ($a1->[$i] ne $a2->[$i]) {
return 0;
}
$i++;
}
return (@$a1 == @$a2);
}
sub to_binary_gray {
my ($n, $radix) = @_;
my $digits = [ digit_split_lowtohigh($n,2) ];
Math::PlanePath::GrayCode::_digits_to_gray_reflected($digits,2);
return digit_join_lowtohigh($digits,2);
}
#------------------------------------------------------------------------------
# A048641 - binary gray cumulative sum
{
my $anum = 'A048641';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my $cumulative = 0;
for (my $n = 0; @got < @$bvalues; $n++) {
$cumulative += to_binary_gray($n);
push @got, $cumulative;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray cumulative sum");
}
#------------------------------------------------------------------------------
# A048644 - binary gray cumulative sum difference from triangular(n)
{
my $anum = 'A048644';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my $cumulative = 0;
for (my $n = 0; @got < @$bvalues; $n++) {
$cumulative += to_binary_gray($n);
push @got, $cumulative - triangular($n);
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray cumulative sum");
}
sub triangular {
my ($n) = @_;
return $n*($n+1)/2;
}
#------------------------------------------------------------------------------
# A048642 - binary gray cumulative product
{
my $anum = 'A048642';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
require Math::BigInt;
my $product = Math::BigInt->new(1);
for (my $n = 0; @got < @$bvalues; $n++) {
$product *= (to_binary_gray($n) || 1);
push @got, $product;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray cumulative product");
}
#------------------------------------------------------------------------------
# A048643 - binary gray cumulative product, diff to factorial(n)
{
my $anum = 'A048643';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
require Math::BigInt;
my $product = Math::BigInt->new(1);
my $factorial = Math::BigInt->new(1);
for (my $n = 0; @got < @$bvalues; $n++) {
$product *= (to_binary_gray($n) || 1);
$factorial *= ($n||1);
push @got, $product - $factorial;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray cumulative product");
}
#------------------------------------------------------------------------------
# A143329 - gray(prime(n)) which is prime too
{
my $anum = 'A143329';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
my $diff;
if ($bvalues) {
for (my $n = 0; @got < @$bvalues; $n++) {
next unless is_prime($n);
my $gray = to_binary_gray($n);
next unless is_prime($gray);
push @got, $gray;
}
$diff = MyOEIS::diff_nums(\@got, $bvalues);
if ($diff) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..45]));
MyTestHelpers::diag ("got: ",join(',',@got[0..45]));
}
}
skip (! $bvalues,
$diff, undef,
"$anum - gray(prime(n)) which is prime too");
}
#------------------------------------------------------------------------------
# A143292 - binary gray of primes
{
my $anum = 'A143292';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
for (my $n = 0; @got < @$bvalues; $n++) {
next unless is_prime($n);
push @got, to_binary_gray($n);
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray of primes");
}
#------------------------------------------------------------------------------
# A005811 - count 1 bits in gray(n), is num runs
{
my $anum = 'A005811';
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
for (my $n = 0; @got < @$bvalues; $n++) {
my $gray = to_binary_gray($n);
push @got, count_1_bits($gray);
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - primes for which binary gray is also prime");
}
sub count_1_bits {
my ($n) = @_;
my $count = 0;
while ($n) {
$count += ($n & 1);
$n >>= 1;
}
return $count;
}
#------------------------------------------------------------------------------
# A173318 - cumulative count 1 bits in gray(n) ie. of A005811
{
my $anum = 'A173318';
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my $cumulative = 0;
for (my $n = 0; @got < @$bvalues; $n++) {
$cumulative += count_1_bits(to_binary_gray($n));
push @got, $cumulative;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - primes for which binary gray is also prime");
}
#------------------------------------------------------------------------------
# A099891 -- triangle cumulative XOR
#
{
my $anum = 'A099891';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my @array;
for (my $y = 0; @got < @$bvalues; $y++) {
my $gray = to_binary_gray($y,$radix);
push @array, [ $gray ];
for (my $x = 1; $x <= $y; $x++) {
$array[$y][$x] = $array[$y-1][$x-1] ^ $array[$y][$x-1];
}
for (my $x = 0; $x <= $y && @got < @$bvalues; $x++) {
push @got, $array[$y][$x];
}
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..10]));
MyTestHelpers::diag ("got: ",join(',',@got[0..10]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1);
}
#------------------------------------------------------------------------------
# A195467 -- diagonals powered permutation, starting from perm^0=identity
#
{
my $anum = 'A195467';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
require Math::PlanePath::Diagonals;
my $diagonal_path = Math::PlanePath::Diagonals->new;
for (my $n = $diagonal_path->n_start; @got < @$bvalues; $n++) {
my ($x, $y) = $diagonal_path->n_to_xy ($n);
my $digits = [ digit_split_lowtohigh($y,$radix) ];
foreach (1 .. $x) { # x=0 unpermuted
Math::PlanePath::GrayCode::_digits_to_gray_reflected($digits,$radix);
}
push @got, digit_join_lowtohigh($digits,$radix);
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..10]));
MyTestHelpers::diag ("got: ",join(',',@got[0..10]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1);
}
#------------------------------------------------------------------------------
# A064706 - binary gray reflected permutation applied twice
{
my $anum = 'A064706';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
for (my $n = 0; @got < @$bvalues; $n++) {
push @got, to_binary_gray(to_binary_gray($n));
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray applied twice");
}
#------------------------------------------------------------------------------
# A055975 - binary gray first diffs
{
my $anum = 'A055975';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my $prev = 0;
for (my $n = 1; @got < @$bvalues; $n++) {
my $digits = [ digit_split_lowtohigh($n,$radix) ];
Math::PlanePath::GrayCode::_digits_to_gray_reflected($digits,$radix);
my $gray = digit_join_lowtohigh($digits,$radix);
push @got, $gray - $prev;
$prev = $gray;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray first diffs");
}
#------------------------------------------------------------------------------
# A055975 - binary gray first diffs
{
my $anum = 'A055975';
my $radix = 2;
my ($bvalues, $lo, $filename) = MyOEIS::read_values($anum);
my @got;
if ($bvalues) {
my $prev = 0;
for (my $n = 1; @got < @$bvalues; $n++) {
my $digits = [ digit_split_lowtohigh($n,$radix) ];
Math::PlanePath::GrayCode::_digits_to_gray_reflected($digits,$radix);
my $gray = digit_join_lowtohigh($digits,$radix);
push @got, $gray - $prev;
$prev = $gray;
}
if (! numeq_array(\@got, $bvalues)) {
MyTestHelpers::diag ("bvalues: ",join(',',@{$bvalues}[0..20]));
MyTestHelpers::diag ("got: ",join(',',@got[0..20]));
}
}
skip (! $bvalues,
numeq_array(\@got, $bvalues),
1, "$anum - binary gray first diffs");
}
#------------------------------------------------------------------------------
exit 0;