Define an additive version of Euler's totient function

Python Help
1

The ordinary Euler’s totient is a multiplicative function, as represented below:

image
image1584×815 189 KB

I want to revise this function into a new additive version as described below:

  1. If p is a prime, then
    phi( p ^ k ) := p ^ k - p ^ (k -1) = p ^ k ( 1- 1/p)

  2. If m and m’ are relatively prime then
    phi( m * m’) := phi(m) + phi(m’)

unless m = 2 and n is odd, in which case
phi(2n) := phi(n)

I want to create this function in python and then compute its possible function values for a given positive integer, for example, phi(6), phi(25), phi(50) and so on.

Any tips for achieving this goal will be appreciated.

Regards,
Zhao

2

Do you know how to write a python program?
If not then start by reading a python tutorial and write some simple code.
For example: The Python Tutorial — Python 3.11.1 documentation

If you know python already what code have you written so far?
What do you need help with?

3

In fact, I worked out a version in GAP language as follows:

OrdersOfCrystallographicRestriction := function(m)
  local fac, div, facExp, ord, x, y; 

  if m mod 2 = 0 and IsOddInt(m / 2) then
    return OrdersOfCrystallographicRestriction(m/2);
  else
    fac:=FactorsInt(m);
    div:=PrimeDivisors(m);
    facExp:=List( div, x -> [x, Size(Filtered(fac, y -> x = y))] );
    ord:=Sum(List(facExp, x -> Phi( x[1]^x[2] ) ));
    return ord;
  fi;  

end;

And it works as expected, for example, I want to find the set of m which meets the following condition OrdersOfCrystallographicRestriction(i) <= 4:

gap> Filtered( [1..100], i -> OrdersOfCrystallographicRestriction(i) <= 4);
[ 1, 2, 3, 4, 5, 6, 8, 10, 12 ]

But I have the following additional conundrum:

  1. I’m not so familiar with the corresponding python functions corresponding to the above version.
  2. For a larger n, say, 50, finding all the set of m such that OrdersOfCrystallographicRestriction(m) <= n, I need to figure out the range of the solution, which seems is not an easy thing.

The following is my attempt, but I don’t know if I have found all solutions:

gap> Filtered( [1..500000], i -> OrdersOfCrystallographicRestriction(i) = 50);
[ 235, 376, 451, 470, 564, 667, 688, 775, 784, 902, 903, 1204, 1216, 1334, 1435, 1443, 1548, 1550, 1720, 1728, 1764, 1767, 1806, 1845, 1924, 1960, 1968, 2035, 2175, 2296, 
  2356, 2580, 2635, 2755, 2870, 2886, 2900, 2940, 2952, 3256, 3264, 3348, 3444, 3451, 3534, 3690, 3915, 4070, 4144, 4147, 4216, 4350, 4408, 4437, 4807, 4884, 4920, 4960, 
  5083, 5270, 5328, 5510, 5824, 6175, 6264, 6324, 6448, 6496, 6612, 6831, 6902, 7395, 7488, 7830, 8294, 8352, 8463, 8775, 8874, 8880, 9200, 9324, 9568, 9614, 9860, 10166, 
  10336, 10360, 11284, 11832, 11935, 12075, 12350, 12480, 12903, 13195, 13320, 13662, 13920, 14508, 14688, 14784, 14790, 15295, 15345, 15540, 15675, 16100, 16120, 16368, 
  16575, 16926, 16965, 17204, 17550, 18096, 19096, 19665, 20097, 20700, 20900, 20976, 20995, 21112, 21735, 22100, 23023, 23870, 24150, 24180, 24288, 24472, 24552, 24633, 
  24871, 25520, 25806, 26390, 26676, 27144, 28215, 28644, 29601, 29700, 29835, 29925, 30590, 30690, 31200, 31248, 31280, 31350, 31464, 31668, 31977, 33150, 33495, 33592, 
  33930, 34776, 35343, 36708, 37400, 39330, 39520, 40194, 40920, 41055, 41990, 43470, 44660, 45144, 45240, 46046, 46368, 46816, 47600, 47736, 49266, 49335, 49504, 49742, 
  50388, 52080, 52440, 53295, 53592, 54740, 56100, 56160, 56430, 57200, 57420, 57456, 59202, 59670, 59850, 60192, 61200, 63648, 63954, 65688, 65780, 66528, 66990, 70380, 
  70686, 71060, 75075, 77280, 78120, 78936, 79800, 82110, 85272, 94185, 95095, 98670, 100100, 100320, 100464, 100980, 101745, 106080, 106590, 107100, 108528, 122265, 
  125664, 128700, 130416, 135135, 141680, 143640, 150150, 150696, 152152, 153153, 162792, 182160, 188370, 190190, 191520, 194480, 195624, 203490, 216216, 228228, 244530, 
  248976, 251160, 255255, 270270, 271320, 277200, 288288, 306306, 318780, 326040, 340340, 408408, 414960, 437580, 480480 ]