Distinct Powers

// https://projecteuler.net/problem=29

// Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
//
// 2^2=4, 2^3=8, 2^4=16, 2^5=32
// 3^2=9, 3^3=27, 3^4=81, 3^5=243
// 4^2=16, 4^3=64, 4^4=256, 4^5=1024
// 5^2=25, 5^3=125, 5^4=625, 5^5=3125
//
// If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
//
// 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
//
// How many distinct terms are there for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
//
// Answer: 9183

// Authored by: Tim Varley 💘
// Assisted-by: Grok Code Fast via Crush 💘 <crush@charm.land>

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

std::string multiply(const std::string& a, int b) {
    std::string result;
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; --i) {
        int prod = (a[i] - '0') * b + carry;
        carry = prod / 10;
        prod %= 10;
        result.push_back(prod + '0');
    }
    while (carry) {
        result.push_back((carry % 10) + '0');
        carry /= 10;
    }
    std::reverse(result.begin(), result.end());
    return result;
}

std::string power(int a, int b) {
    std::string result = "1";
    for (int i = 0; i < b; ++i) {
        result = multiply(result, a);
    }
    return result;
}

int distinct_powers(int max_a, int max_b) {
    std::set<std::string> terms;
    for (int a = 2; a <= max_a; ++a) {
        for (int b = 2; b <= max_b; ++b) {
            terms.insert(power(a, b));
        }
    }
    return terms.size();
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << distinct_powers(100, 100) << std::endl;
}
#endif // UNITTEST_MODE

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

public class Solution029 implements Solution {
  public String solve() {
    Set<BigInteger> distinct = new HashSet<>();

    for (int a = 2; a <= 100; a++) {
      for (int b = 2; b <= 100; b++) {
        distinct.add(BigInteger.valueOf(a).pow(b));
      }
    }

    return Integer.toString(distinct.size());
  }
}

module.exports = {
  answer: () => {
    const distinct = new Set();

    for (let a = 2; a <= 100; a++) {
      for (let b = 2; b <= 100; b++) {
        distinct.add(BigInt(a) ** BigInt(b));
      }
    }

    return distinct.size;
  }
};

def solve():
    """
    Distinct powers
    Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5.
    If they are then placed in numerical order, with any repeats removed, we get the
    following sequence of 15 distinct terms.
    How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
    https://projecteuler.net/problem=29
    """
    return len({a**b for a in range(2, 101) for b in range(2, 101)})

require 'set'

# Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
#
# 2^2=4, 2^3=8, 2^4=16, 2^5=32
# 3^2=9, 3^3=27, 3^4=81, 3^5=243
# 4^2=16, 4^3=64, 4^4=256, 4^5=1024
# 5^2=25, 5^3=125, 5^4=625, 5^5=3125
#
# If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
#
# 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
#
# How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
#
# Answer: 9183
def euler029_solution
  powers = Set.new
  (2..100).each do |a|
    (2..100).each do |b|
      powers.add(a**b)
    end
  end
  powers.size
end

puts euler029_solution if __FILE__ == $PROGRAM_NAME

package main

import (
    "fmt"
    "math/big"
)

func main() {
    seen := make(map[string]bool)
    for a := 2; a <= 100; a++ {
        for b := 2; b <= 100; b++ {
            val := new(big.Int).Exp(big.NewInt(int64(a)), big.NewInt(int64(b)), nil)
            seen[val.String()] = true
        }
    }
    fmt.Println(len(seen))
}

// https://projecteuler.net/problem=29
//
// Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
// 2^2=4, 2^3=8, 2^4=16, 2^5=32
// 3^2=9, 3^3=27, 3^4=81, 3^5=243
// 4^2=16, 4^3=64, 4^4=256, 4^5=1024
// 5^2=25, 5^3=125, 5^4=625, 5^5=3125
//
// If they are then placed in numerical order, with any repeats removed, we get a
// sequence of 15 distinct terms.
//
// How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 5 and
// 2 ≤ b ≤ 5? (Problem asks for 2 ≤ a,b ≤ 100)
//
// Answer: 9183

fn multiply_vec(digits: &[u32], factor: u64) -> Vec<u32> {
    let mut result = digits.to_vec();
    let mut carry = 0u64;
    for d in result.iter_mut() {
        let val = *d as u64 * factor + carry;
        *d = (val % 10) as u32;
        carry = val / 10;
    }
    while carry > 0 {
        result.push((carry % 10) as u32);
        carry /= 10;
    }
    result
}

pub fn distinct_powers(limit: u64) -> usize {
    use std::collections::HashSet;
    let mut seen: HashSet<Vec<u32>> = HashSet::new();
    for a in 2..=limit {
        let mut power = vec![1u32];
        for b in 1..=limit {
            power = multiply_vec(&power, a);
            if b >= 2 {
                seen.insert(power.clone());
            }
        }
    }
    seen.len()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_029() {
        assert_eq!(distinct_powers(5), 15);
        assert_eq!(distinct_powers(100), 9183);
    }
}