#!/usr/bin/perl -w

# Copyright 2010, 2011, 2014 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.010;
use strict;
use warnings;
use Math::Factor::XS 0.39 'factors', 'prime_factors'; # version 0.39 for prime_factors()
use List::MoreUtils 'uniq';
use Math::PlanePath::CoprimeColumns;

{
  my $coprime = sub {
    my ($x,$y) = @_;
    return $x > 0 && Math::PlanePath::CoprimeColumns::_coprime($x,$y);
  };
  foreach my $n (2*2*2*3, 3*3*3*5) {
    my $tot = Math::PlanePath::CoprimeColumns::_totient($n);
    my @factors = uniq(prime_factors($n));
    my $factors_str = join(',',@factors);
    print "n=$n  totient=$tot  factors=$factors_str\n";
    my @coprimes = grep {$coprime->($_,$n)} 0 .. $n-1;
    my @coprime_dots = map {($coprime->($_,$n)?'*':'_')
                              .($_ % 3 == 2 ? ',' : '')} 0 .. $n-1;
    my $want_str = join(',',@coprimes);
    my $dots_str = join('',@coprime_dots);
    print "dots $dots_str\n";
    print "want $want_str\n";
    my @got;
    foreach my $i (0 .. $#coprimes) {
      my $c = $i+1;
      foreach my $f (@factors) {
        $c += int($i/($f-1));
      }
      push @got, $c;
    }
    my $got_str = join(',',@got);
    my $diff = ($want_str eq $got_str ? '' : ' ***');
    print "got  $got_str$diff";
    print "\n";
    print "\n";
  }
  exit 0;
}

{
  require Math::PlanePath::CoprimeColumns;
  my $n = 0;
  foreach my $x (3 .. 1000) {
    foreach my $y (1 .. $x-1) {
      $n += Math::PlanePath::CoprimeColumns::_coprime($x,$y);
    }
    my $square = $x*$x;
    my $frac = $n / $square;
    printf "%d %d  %d %.3g\n", $x, $n, $square, $frac;
  }
  exit 0;
}
{
  require Math::PlanePath::CoprimeColumns;
  foreach my $x (2 .. 100) {
    my $n = 0;
    my @list;
    foreach my $y (1 .. $x-1) {
      if (Math::PlanePath::CoprimeColumns::_coprime($x,$y)) {
        $n++;
        push @list, $y;
      }
    }
    my $c = Math::PlanePath::CoprimeColumns::_totient_count($x);
    if ($c != $n) {
      die "x=$x  tot $c step $n\n";
    }
    printf "%d %d   %s\n", $x, $n, join(',',@list);
  }
  exit 0;
}




sub _coprime {
  my ($x, $y) = @_;
  ### _coprime(): "$x,$y"
  if ($x < $y) {
    ($x,$y) = ($y,$x);
  }
  for (;;) {
    if ($y <= 0) {
      return 0;
    }
    if ($y == 1) {
      return 1;
    }
    $x %= $y;
    ($x,$y) = ($y,$x);
  }
}