#!/usr/bin/env perl
use v5.20;
use utf8;
use strict;
use warnings;
use feature qw(say signatures);
no warnings 'experimental::signatures';

use Carp qw(croak);
use Scalar::Util qw(looks_like_number);

use Getopt::Long qw(:config auto_help);
use Pod::Usage;

{
    my $N;
    GetOptions(
        '<>' => sub($arg) {
            die "exactly one positive integer expected!\n"
              if defined $N
              || !looks_like_number($arg)
              || $arg < 1
              || int($arg) != $arg;
            $N = $arg;
        }
      )
      && defined $N
      or pod2usage( -exitval => 1 );

    say power_of_two($N) ? 1 : 0;
}

sub power_of_two ($n ) {

    # edge case
    # a = 1, b = 2, a ^ b = 1 = $n
    return 1 if $n == 1;

    # calculate sqrt as upper bound and check if $n is a quadratic number
    # $floored_sqrt ^ 2 = $n
    my $sqrt         = sqrt($n);
    my $floored_sqrt = int($sqrt);
    return 1 if $floored_sqrt == $sqrt;

    # n  = a ^ b
    # log'a(n) = b
    # for bases(a) from 2 to $floored_sqrt, check if we can find an integer
    # exponent (b) so that a ^ b = $n
    return generator_any(
        sub($a) {
            my $maybe_b = logarithm( $a, $n );
            if ( int($maybe_b) == $maybe_b ) {
                say "FOUND: $a ^ $maybe_b = $n" if $ENV{DEBUG};
                return 1;
            }
        },
        mk_number_gen( 2, $floored_sqrt )
    );
}

#            log'a(x)
# log'b(x) = ------
#            log'a(b)
sub logarithm ( $base, $numerus ) {
    return $numerus == 1 ? 1 : croak "cannot calculate log'$base($numerus)"
      if $base == 1;
    return log($numerus) / log($base);
}

# check wether any of the values generated by $gen fullfills $cond
# exhausts the generator up to the first value that fullfills $cond
sub generator_any ( $cond, $gen ) {
    for ( my $n = $gen->() ; defined($n) ; $n = $gen->() ) {
        return 1 if $cond->($n);
    }
}

# lazily generate a stream of numbers from $start to $end
# returns a sub ref that can be called to generate the next value until
# exhaustion. when the generator is exhausted `undef` will be returned on each
# subsequent call
sub mk_number_gen ( $start, $end ) {
    return sub {
        state $cur = $start;
        return $cur <= $end ? $cur++ : undef;
    };
}

=pod

=head1 NAME

wk-085 ch-2 - Triplet Sum

=head1 SYNOPSIS

ch-2.pl [options] <N>

  This program will print 1 if N can be expressed as a^b with a > 0
  and b > 1

  Arguments:
    <N>          a positive integer

  Options:
    --help       print this help text

=cut