fourier-transform/main.cpp

/*
	Calculates the optimal fourier transform(s) for a number
	Also outputs distribution of least-fouerist-base
	Inspired by http://www.smbc-comics.com/?id=2874

	A very naive implementation :)
*/

#include <map>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int length(int number, int base){
	int length = 1;
	int acc = base;

	while(number >= acc){
		length++;
		acc *= base;
	}

	return length;
}

int fours(int number, int base){
	int count = (number % base) == 4;

	while(number > base){
		number /= base;
		if(number % base == 4) count++;
	}

	return count;
}

// Performs a fourier transform to make the input fourier
// Done with a linear search, there are probably betters ways
// There is not always a unique base in which the input is fouriest, so we output a vector
vector<int> fourier(int input){
	int base = 1;
	int current_best = 0;
	vector<int> bests{};

	do {
		base++;
		int current = fours(input, base);
		if(current >= current_best){
			if(current > current_best){
				bests.clear();
				current_best = current;
			}
			bests.push_back(base);
		}
	} while(length(input, base) > 1);

	return bests;
}

// The input number is shown, then the fouriness, then the bases in which the input is fouriest.
int main(){
	map<int, int> distribution;

	cout << "Number, \t Fouriness, \t Possible bases" << endl;
	for(int i = 1; i < 1000; i++){
		auto bases = fourier(i);
		auto nfours = fours(i, bases.back());

		distribution[bases.front()]++;

		cout << setw(5) << i << ", \t" << setw(5) << nfours << ", \t[ ";
		copy(begin(bases), end(bases), ostream_iterator<int>(cout, " "));
		cout << "]" << endl;
	}

	cout << "\nDistribution of least bases" << endl;
	for(auto x : distribution){
		cout << x.first << ", \t" << x.second << endl;
	}
}