Problem of the Month (May 2011)

Suppose f and g are integer functions, with f(n) ≤ n and g(n) ≥ n. For small integers 0 ≤ n ≤ 100, we ask for the smallest number of iterations of f or g to return to n. We also ask for the smallest number n requiring k operations to return to n. Some pairs of functions are more interesting than others. We restrict our attention to pairs which have relatively few cycles. Can you extend one of the tables below, or find another interesting pair of functions f and g?

ANSWERS

Berend van der Zwaag sent solutions this month.

φ(n) = number of smaller coprime numbers to n, σ(n) = sum of divisors of n
φ(0)=0 σ(1)=1 φ(σ(2))=2 σ(φ(3))=3 σ(σ(φ(4)))=4
φ(σ(φ(σ(6))))=6 σ(φ(σ(7)))=7 φ(σ(8))=8 φ(σ(12))=12 σ(φ(15))=15
φ(σ(σ(16)))=16 σ(σ(φ(24)))=24 σ(φ(28))=28 φ(σ(φ(σ(φ(σ(30))))))=30 σ(φ(σ(31)))=31
σ(σ(φ(32)))=32 φ(σ(φ(σ(σ(σ(φ(36)))))))=36 φ(σ(φ(σ(48))))=48 σ(σ(φ(φ(σ(φ(σ(56)))))))=56 φ(σ(φ(σ(60))))=60
σ(σ(σ(φ(φ(σ(63))))))=63 φ(σ(σ(64)))=64 φ(σ(φ(σ(72))))=72 σ(φ(σ(φ(φ(σ(σ(91)))))))=91 φ(φ(σ(σ(96))))=96

operationssequence
1φ(0)=0
2φ(σ(2))=2
3σ(σ(φ(4)))=4
4φ(σ(φ(σ(6))))=6
5φ(σ(σ(σ(φ(144)))))=144
6φ(σ(φ(σ(φ(σ(30))))))=30
7φ(σ(φ(σ(σ(σ(φ(36)))))))=36
8φ(σ(φ(σ(σ(σ(φ(σ(384))))))))=384
9φ(φ(σ(φ(φ(σ(σ(σ(σ(800)))))))))=800
10φ(φ(σ(φ(φ(φ(σ(σ(σ(σ(160))))))))))=160
11φ(σ(φ(φ(σ(φ(φ(σ(σ(σ(σ(108)))))))))))=108
12φ(σ(φ(φ(σ(φ(σ(φ(σ(σ(σ(φ(1080))))))))))))=1080
13φ(φ(φ(σ(φ(σ(σ(φ(σ(σ(φ(σ(σ(640)))))))))))))=640 (BZ)
14φ(σ(σ(σ(φ(φ(φ(σ(φ(σ(σ(φ(φ(σ(4620))))))))))))))=4620 (BZ)
15φ(σ(σ(σ(φ(φ(φ(σ(φ(φ(σ(σ(σ(φ(σ(10800)))))))))))))))=10800 (BZ)
16φ(σ(σ(σ(σ(φ(σ(φ(φ(σ(φ(σ(φ(φ(σ(φ(10496))))))))))))))))=10496 (BZ)
17σ(φ(φ(σ(φ(σ(σ(σ(φ(σ(φ(σ(φ(σ(σ(φ(φ(7905)))))))))))))))))=7905 (BZ)
18φ(σ(σ(φ(σ(σ(σ(φ(φ(φ(σ(φ(σ(φ(σ(σ(σ(φ(23760))))))))))))))))))=23760 (BZ)

√(n) = square root rounded down, F(n) = n!
√(0)=0 F(1)=1 F(2)=2
√(√(F(√(√(F(F(3)))))))=3 √(F(4))=4 √(√(F(F(√(√(F(5)))))))=5
F(√(√(F(√(√(F(6)))))))=6 √(F(√(√(F(F(√(10)))))))=10 √(√(√(F(12))))=12
√(√(√(√(√(√(√(F(√(√(√(√(F(√(√(√(√(F(F(√(21))))))))))))))))))))=21 (BZ) F(√(24))=24 √(F(F(√(√(F(√(26)))))))=26
√(√(√(√(F(F(√(√(√(√(√(√(√(√(F(√(√(√(√(F(30))))))))))))))))))))=30 (BZ) √(√(√(√(√(√(√(F(F(√(35))))))))))=35 √(√(F(√(F(√(√(F(√(43)))))))))=43
√(√(√(√(√(F(√(√(F(√(F(√(√(F(√(44)))))))))))))))=44 √(√(√(√(F(√(F(√(46))))))))=46 √(√(√(√(√(F(√(82)))))))=82

operationssequence
1√(0)=0
2√(F(4))=4
3none
4√(√(√(F(12))))=12
5none
6none
7√(√(F(√(√(F(F(3)))))))=3
8√(√(√(√(F(√(F(√(46))))))))=46
9√(√(F(√(F(√(√(F(√(43)))))))))=43
10√(√(√(√(√(√(√(F(F(√(35))))))))))=35
11none

Π(n) = product of digits of n, S(n) = n2
Π(0)=0 Π(1)=1 Π(2)=2 Π(3)=3 Π(4)=4
Π(5)=5 Π(6)=6 Π(7)=7 Π(8)=8 Π(9)=9
Π(Π(S(Π(S(S(Π(16)))))))=16 Π(S(Π(Π(Π(Π(Π(S(S(Π(S(18)))))))))))=18 Π(S(Π(24)))=24 S(Π(Π(Π(S(Π(S(36)))))))=36 S(Π(Π(64)))=64

operationssequence
1Π(0)=0
2none?
3Π(S(Π(24)))=24
4none?
5none?
6Π(Π(Π(S(Π(S(128))))))=128
7Π(Π(S(Π(S(S(Π(16)))))))=16
8none?
9none?
10none?
11Π(S(Π(Π(Π(Π(Π(S(S(Π(S(18)))))))))))=18
12none?

Σ(n) = sum of digits of n, P(n) = 2n
Σ(0)=0 Σ(1)=1 Σ(2)=2
Σ(3)=3 Σ(4)=4 Σ(5)=5
Σ(6)=6 Σ(7)=7 Σ(8)=8
Σ(9)=9 Σ(P(Σ(P(P(Σ(11))))))=11 Σ(Σ(P(P(Σ(P(Σ(13)))))))=13
Σ(P(Σ(P(Σ(P(Σ(P(P(14)))))))))=14 P(P(Σ(Σ(P(Σ(16))))))=16 Σ(P(Σ(Σ(P(P(Σ(P(P(Σ(20))))))))))=20
Σ(P(Σ(P(Σ(P(Σ(P(Σ(22)))))))))=22 Σ(P(P(P(Σ(Σ(P(Σ(25))))))))=25 Σ(P(Σ(P(P(P(Σ(Σ(29))))))))=29
Σ(P(Σ(P(Σ(Σ(P(P(Σ(P(Σ(31)))))))))))=31 P(Σ(32))=32 Σ(P(Σ(P(Σ(P(P(Σ(Σ(Σ(P(P(Σ(41)))))))))))))=41
Σ(P(Σ(P(Σ(P(Σ(Σ(P(P(Σ(Σ(P(Σ(47))))))))))))))=47 Σ(P(Σ(P(Σ(P(Σ(P(P(Σ(Σ(Σ(P(50)))))))))))))=50 Σ(P(P(Σ(Σ(P(Σ(P(Σ(Σ(P(58)))))))))))=58
Σ(P(Σ(P(Σ(P(Σ(P(Σ(Σ(P(P(Σ(Σ(68))))))))))))))=68 Σ(P(70))=70 Σ(P(Σ(P(Σ(P(Σ(P(Σ(P(P(Σ(Σ(76)))))))))))))=76

operationssequence
1Σ(0)=0
2P(Σ(32))=32
3none
4none
5none
6Σ(P(Σ(P(P(Σ(11))))))=11
7Σ(Σ(P(P(Σ(P(Σ(13)))))))=13
8Σ(P(P(P(Σ(Σ(P(Σ(25))))))))=25
9Σ(P(Σ(P(Σ(P(Σ(P(P(14)))))))))=14
10Σ(P(Σ(Σ(P(P(Σ(P(P(Σ(20))))))))))=20
11Σ(P(Σ(P(Σ(Σ(P(P(Σ(P(Σ(31)))))))))))=31
12none?
13Σ(P(Σ(P(Σ(P(P(Σ(Σ(Σ(P(P(Σ(41)))))))))))))=41
14Σ(P(Σ(P(Σ(P(Σ(Σ(P(P(Σ(Σ(P(Σ(47))))))))))))))=47

Berend van der Zwaag was interested in these two functions:

p(n) = smallest permutation of the digits of n, d(n) = 2n
p(0)=0 p(1)=1 p(2)=2
p(3)=3 p(4)=4 p(5)=5
p(6)=6 p(7)=7 p(8)=8
p(9)=9 d(p(d(d(p(d(d(d(d(d(d(d(d(d(10))))))))))))))=10 d(d(p(d(d(p(d(d(d(d(d(d(d(d(20))))))))))))))=20
d(p(d(p(d(d(d(p(d(d(d(d(d(30)))))))))))))=30 d(p(d(d(d(d(d(d(d(p(d(d(d(d(32))))))))))))))=32 d(d(d(p(d(d(p(d(d(d(d(d(d(d(40))))))))))))))=40
d(p(d(p(d(d(d(d(d(d(d(d(d(d(50))))))))))))))=50 d(p(d(d(p(d(54))))))=54 d(d(p(d(p(d(d(d(p(d(d(d(d(60)))))))))))))=60
d(d(p(d(d(d(d(d(d(d(p(d(d(d(64))))))))))))))=64 d(d(p(d(d(p(72))))))=72 d(p(d(d(d(d(p(d(d(d(d(p(d(d(d(76)))))))))))))))=76
d(d(d(d(p(d(d(p(d(d(d(d(d(d(80))))))))))))))=80 d(p(d(p(d(d(d(90)))))))=90 d(p(d(d(p(d(p(d(d(d(d(p(d(p(d(d(d(92)))))))))))))))))=92
d(p(d(d(d(d(p(d(d(d(p(96)))))))))))=96 d(p(d(p(d(p(d(d(d(p(98))))))))))=98 d(d(p(d(p(d(d(d(d(d(d(d(d(d(100))))))))))))))=100

operationssequence
1p(0)=0
2d(p(2491578))=2491578
3d(p(d(24913578)))=24913578
4d(p(d(p(24691578))))=24691578
5d(p(d(d(d(252)))))=252
6d(p(d(d(p(d(54))))))=54
7d(p(d(p(d(d(d(90)))))))=90
8d(p(d(d(d(d(p(d(298))))))))=298
9d(p(d(d(d(p(d(d(p(254)))))))))=254
10d(p(d(p(d(p(d(d(d(p(98))))))))))=98
11d(p(d(d(d(d(p(d(d(d(p(96)))))))))))=96
12d(p(d(p(d(d(d(d(d(d(d(d(450))))))))))))=450
13d(p(d(p(d(d(d(p(d(d(d(d(d(30)))))))))))))=30
14d(p(d(d(p(d(d(d(d(d(d(d(d(d(10))))))))))))))=10
15d(p(d(d(d(d(p(d(d(d(d(p(d(d(d(76)))))))))))))))=76
16d(p(d(p(d(d(d(d(p(d(p(d(d(d(d(d(230))))))))))))))))=230
17d(p(d(d(p(d(p(d(d(d(d(p(d(p(d(d(d(92)))))))))))))))))=92
18d(d(p(d(p(d(p(d(d(d(d(p(d(d(p(d(d(p(1396))))))))))))))))))=1396
19d(d(p(d(d(d(d(p(d(d(d(d(d(d(p(d(p(d(d(1836)))))))))))))))))))=1836
20d(p(d(d(d(d(p(d(d(d(d(d(d(d(d(p(d(d(d(p(696))))))))))))))))))))=696

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 5/17/11.