// ////////////////////////////////////////////////////////
// # Title
// Distinct powers
//
// # URL
// https://projecteuler.net/problem=29
// http://euler.stephan-brumme.com/29/
//
// # Problem
// 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 ab for `2 <= a <= 100` and `2 <= b <= 100`?
//
// # Solved by
// Stephan Brumme
// February 2017
//
// # Algorithm
// The core problem is: find all `x^y` where also an `a^b` exists with `x>a` and `x <= limit` (a "collision").
// The only collision in the problem's example is `x^y=4^2=16` and `a^b=2^4=2^4=16`.
// My variable ''repeated'' counts all numbers that appear repeatedly (such as `16`).
// The final result will be `(limit-1)^2 - repeated` (for the example we found that `repeated=1` and therefore `(5-1)^2 - 1 = 15`).
//
// The rest of this algorithm is all about an efficient way to find the value of `repeated`.
//
// __Note:__ we have `limit=5` in the example but we need to solve for `limit=100` (or `limit=100000` in the modified Hackerrank problem).
//
// Because of `4=2^2` we know that `4^y=2^{2y}`: all powers with base `4` can be rewritten as `4^2=2^{2*2}=2^4`, `4^3=2^{2*3}=2^6`, `4^4=2^{2*4}=2^8` and `4^5=2^{2*5}=2^{10}`.
// Therefore when we convert all powers of `4` to powers of `2` we use those exponents: ''2,3,4,5'' (for `a=2`) and ''4,6,8,10'' (for `x=4` ==> `a=2^2`).
// Obviously ''4'' is found in both sets. That's our collision.
//
// The first step in my program is to find all exponents if we reduce all numbers `x` to their "parent" `a^b`:
// 1. we know for certain that all numbers from `2` to `limit` will be used: ''2,3,4,5''
// 2. if `x=a^2` is a valid base (that means `x <= limit`), then ''2*2,2*3,2*4,2*5'' will be used for base `a`, too.
// 3. if `x=a^3` is a valid base then ''3*2,3*3,3*4,3*5'' will be used for base `a`, too.
// 4. if `x=a^4` is a valid base then ''4*2,4*3,4*4,4*5'' will be used for base `a`, too.
// 5. and so on ...
//
// My container ''minExponent'' records which exponents could be used. If there are multiple combinations, then the lowest is stored.
// I hope an example makes things a bit clearer:
// 1. insert ''1'' at positions ''2,3,4,5''
// 2. insert ''2'' at positions ''6,8,10'' ==> but not at position 4 because that one is already occupied
// 3. we can stop because there is no other base `x=2^3 <= limit`
//
// ''minExponent'' contains ''2 ==> 1, 3 ==> 1, 4 ==> 1, 5 ==> 1, 6 ==> 2, 8 ==> 2, 10 ==> 2''
// An ''std::vector'' doesn't have gaps and starts at 0, that's why I there are some unused entries, too, filled with zero:
// ''minExponent = { 0, 0, 1, 1, 1, 1, 2, 0, 2, 0, 2 }''
//
// The "highest" collision with base `2^b=x^y` can be found for `2^b=64^y=2^{8y}` (next power of 2 is 128, which is larger than 100).
// For the modified Hackerrank problem, this "highest" collision with base `2^b=x^y` can be found for `x^y=65536^y=2^{16y}` (limit is 100000 instead of 100).
// That's why ''MaxBasePower = 16''.
//
// My container ''base'' is zero for every ''base[x]'' where there no `a^b=x` exists. The data structure is incrementally updated and initially all entries are zero.
// If we encounter such a ''base[x]=0'' then we immediately fill ''base[x*x]=x'' and ''base[x*x*x]=x'' and ''base[x*x*x*x]=x'' ...
// because ''x*x'', ''x*x*x'', ... will collide with ''x''.
// In the example, for ''x=2'' we'll find that ''base[2]=0'' and hence fill ''base[2*2]=2''.
// If ''base[x] == 0'' then collisions with smaller x are impossible.
//
// If ''base[x] != 0'' then ''x'' has a "parent" such that `x=base[x]^exponent`. Collisions are possible.
// We scan through ''minExponent'' and count all collisions (in ''repeated''):
// Due to `x^y = base[x]^{y*exponent}` all elements ''minExponent[y*exponent]'' have to be checked if that entry was
// already used by some other ''x''.
//
// # Alternative
// The original problem can be solved by brute-force if your language supports big integers.
// I haven't tried it but maybe you can store `log{a^b}` in a ''std::set'', too.
//
// # Hackerrank
// The higher limit of 100000 instead of 100 forced me to come up with my slightly more complex but much faster solution.
// The result exceeds 32 bits (for limit close to 100000), that's why I introduced the ''all'' variable as ''unsigned long long''.
#include
#include
int main()
{
// I called it "limit" in the explanation
unsigned int maxExponent;
std::cin >> maxExponent;
// 2^17 > 10^5 (max. input)
const unsigned int MaxBasePower = 16;
// if a^b = base^(exponent*basePower)
// then b = (1..n) but exponent*basePower = (basePower, 2*basePower, 3*basePower, ..., n*basePower)
// store for each product exponent*basePower the smallest basePower
std::vector minExponent((maxExponent+1)*MaxBasePower);
for (unsigned int i = 1; i <= MaxBasePower; i++)
for (unsigned int j = 1; j <= maxExponent; j++)
if (minExponent[i*j] == 0)
minExponent[i*j] = i;
// all "a" which can be composed as base^exponent, stored as [a] => [base]
std::vector base(maxExponent + 1, 0);
// how often numbers were used multiple times (those are the collisions we are looking for)
unsigned int repeated = 0;
// analyze all bases
for (unsigned int x = 2; x <= maxExponent; x++) // maximum base is maxExponent, too
{
// is x = parent^exponent ?
auto parent = base[x];
if (parent == 0) // no
{
// find all future children where "x" is the parent
auto power = x * x;
// [x^2] = [x^3] = [x^4] = ... = x
while (power <= maxExponent)
{
base[power] = x;
power *= x;
}
// no x=a^b possible, "repeated" remains unchanged
continue;
}
// we have a parent, find exponent such that a = parent^exponent
unsigned int exponent = 0;
auto reduce = x;
while (reduce > 1)
{
reduce /= parent;
exponent++;
}
// analyze all pairs, and count all numbers we saw before (repeated++)
for (unsigned int y = 2; y <= maxExponent; y++)
{
// that exponent was already used ?
if (minExponent[y * exponent] < exponent)
repeated++;
}
}
// there are (maxExponent-1)^2 combinations, subtract all duplicates
unsigned long long all = maxExponent - 1;
auto result = all*all - repeated;
std::cout << result << std::endl;
return 0;
}