# PerfectPower

A mathematical library for detecting perfect powers in Elixir.

A perfect power is a positive integer that can be expressed as an integer power of another positive integer. More formally, a perfect power is a number n that can be written as $n = a^b$ where a and b are integers greater than 1.

## Installation

The package can be installed by adding `perfect_power` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:perfect_power, "~> 1.0"}
  ]
end
```

## Usage

```elixir
# Check if a number is a perfect power
PerfectPower.exponential_form?(4)   # true  (2^2)
PerfectPower.exponential_form?(8)   # true  (2^3)
PerfectPower.exponential_form?(16)  # true  (2^4 or 4^2)
PerfectPower.exponential_form?(27)  # true  (3^3)
PerfectPower.exponential_form?(100) # true  (10^2)

# Numbers that are not perfect powers
PerfectPower.exponential_form?(2)   # false (prime)
PerfectPower.exponential_form?(7)   # false (prime)
PerfectPower.exponential_form?(6)   # false (2×3)
PerfectPower.exponential_form?(10)  # false (2×5)
```

## Mathematical Background

### What are Perfect Powers?

Perfect powers are numbers that can be written as $a^b$ where both a and b are integers greater than 1. They include:

- **Perfect squares**: 4 ($2^2$), 9 ($3^2$), 16 ($4^2$), 25 ($5^2$), 36 ($6^2$), 49 ($7^2$), 64 ($8^2$), 81 ($9^2$), 100 ($10^2$)
- **Perfect cubes**: 8 ($2^3$), 27 ($3^3$), 64 ($4^3$), 125 ($5^3$), 216 ($6^3$), 343 ($7^3$), 512 ($8^3$), 729 ($9^3$), 1000 ($10^3$)
- **Higher powers**: 16 ($2^4$), 32 ($2^5$), 64 ($2^6$), 128 ($2^7$), 256 ($2^8$), 512 ($2^9$), 1024 ($2^{10}$), 81 ($3^4$), 243 ($3^5$), 729 ($3^6$), 625 ($5^4$), 3125 ($5^5$)

### Numbers that are NOT Perfect Powers

- **Prime numbers**: 2, 3, 5, 7, 11, ...
- **Products of different primes**: 6 ($2 \times 3$), 10 ($2 \times 5$), 14 ($2 \times 7$), 15 ($3 \times 5$), ...

### Edge Cases

- **0 and 1**: By convention, 0 and 1 are considered perfect powers (0 = $0^2$, 1 = $1^2$)

## Algorithm

The library uses an optimized algorithm to efficiently determine if a number is a perfect power:

1. **Edge case handling**: 0, 1, 2, and 3 are handled with explicit pattern matching
2. **Mathematical bounds**: For other numbers, the algorithm checks potential bases from 2 up to the square root of the number
3. **Logarithmic calculation**: For each potential base, it calculates the corresponding exponent using logarithms
4. **Verification**: It verifies if the calculated exponent produces the original number

### Performance Characteristics

- **Time complexity**: $O(\log n)$ for most numbers
- **Space complexity**: $O(1)$
- **Mathematical optimization**: Uses logarithmic bounds to limit search space
- **Efficient for large numbers**: Can handle numbers up to $2^512$ and beyond

## Examples

### Perfect Powers

```elixir
# Perfect squares
PerfectPower.exponential_form?(4)   # true  (2²)
PerfectPower.exponential_form?(9)   # true  (3²)
PerfectPower.exponential_form?(16)  # true  (4²)

# Perfect cubes
PerfectPower.exponential_form?(8)   # true  (2³)
PerfectPower.exponential_form?(27)  # true  (3³)
PerfectPower.exponential_form?(64)  # true  (4³)

# Higher powers
PerfectPower.exponential_form?(16)  # true  (2⁴)
PerfectPower.exponential_form?(32)  # true  (2⁵)
PerfectPower.exponential_form?(64)  # true  (2⁶)
PerfectPower.exponential_form?(128) # true  (2⁷)
```

### Non-Perfect Powers

```elixir
# Prime numbers
PerfectPower.exponential_form?(2)   # false
PerfectPower.exponential_form?(3)   # false
PerfectPower.exponential_form?(5)   # false

# Composite numbers that are not perfect powers
PerfectPower.exponential_form?(6)   # false (2×3)
PerfectPower.exponential_form?(10)  # false (2×5)
PerfectPower.exponential_form?(14)  # false (2×7)
```

### Large Numbers

```elixir
# Huge perfect powers
PerfectPower.exponential_form?(Bitwise.bsl(1, 256)) # true  (2²⁵⁶)
PerfectPower.exponential_form?(Bitwise.bsl(1, 512)) # true  (2⁵¹²)
```

## Testing

Run the test suite:

```bash
mix test
```

The test suite includes comprehensive coverage of:
- Perfect squares, cubes, and higher powers
- Prime numbers (up to 997)
- Composite non-perfect powers
- Edge cases (0, 1, 2, 3)
- Large numbers for performance testing

## Documentation

Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc):

```bash
mix docs
```

## License

Copyright (c) 2025 University of Kitakyushu

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at [http://www.apache.org/licenses/LICENSE-2.0](http://www.apache.org/licenses/LICENSE-2.0)

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.