Wu Yudong's Blog

Totient permutation

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

欧拉总计函数与重排

在小于n的数中，与n互质的数的数目记为欧拉总计函数φ(n)（有时也称为φ函数）。例如，因为1、2、4、5、7和8均小于9且与9互质，故φ(9)=6。

1被认为和任意正整数互质，所以φ(1)=1。

有趣的是，φ(87109)=79180，而79180恰好是87109的一个重排。

在1 < n < 10⁷中，有些n满足φ(n)是n的一个重排，求这些取值中使n/φ(n)最小的一个。

//（Problem 70）Totient permutation
// Completed on Tue, 18 Feb 2014, 11:06
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<stdbool.h>

#define N 10000000

int phi[N];	//数组中储存每个数的欧拉数

int cmp(const void *a, const void *b)
{
	return (*(char *)a - *(char *)b);
}

void genPhi(int n)	//求出比n小的每一个数的欧拉数(n-1的)
{
	int i, j, pNum = 0;
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for (i = 2; i < n; i++) {
		if (!phi[i]) {
			for (j = i; j < n; j += i) {
				if (!phi[j])
					phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
}

int fun(int n)					//计算整数n的位数
{
	return (log10(n * 1.0) + 1);
}

bool compare(int n, int m)		//判断两整数是否其中一个是另一个的排列数
{
	int i, L1, L2;
	char from[10], to[10];
	sprintf(from, "%lld", m);
	sprintf(to, "%lld", n);
	L1 = strlen(from);
	L2 = strlen(to);
	qsort(from, L1, sizeof(from[0]), cmp);
	qsort(to, L2, sizeof(to[0]), cmp);
	return !strcmp(from, to);
}

void solve()
{
	int i, j, count, k;
	double min, t;
	min = 10.0;
	for (i = 2; i < N; i++) {
		if ((fun(i) == fun(phi[i])) && compare(i, phi[i])) {
			t = i * 1.0 / phi[i];
			if (t < min) {
				min = t;
				k = i;
			}
		}
	}
	printf("%d\n", k);
}

int main()
{
	genPhi(N);
	solve();
	return 0;
}