Cerca fra gli articoli

φ(n)

Indice

La funzione φ(n) oscilla infinite volte tra n – 1 (quando n è primo) e un limite inferiore che cresce come nloglogn; più precisamente Limite superiore per il valore di φ(n) / n e Limite inferiore per il valore di φ(n) * log(log(n)) / n (E. Landau, 1909).

φ(n) assume infinite volte valori inferiori a n / (e^γ * log(log(n))) , ma per ε > 0 e n abbastanza grande, non è mai inferiore a (1 – ε) * n / (e^γ * log(log(n))) (J.-L. Nicolas, 1983).

La dimostrazione di Nicolas è composta da due parti: la prima suppone vera l’ipotesi di Riemann, la seconda la suppone falsa; in quest’ultimo caso esisterebbero infiniti primi p tali che φ(p#) ≥ p# / (e^γ * log(log(p#))) .

Limite inferiore per il valore di φ(n + 1) / φ(n) e Limite superiore per il valore di φ(n + 1) / φ(n) (Somayajulu, 1950).

Nonostante il comportamento selvaggio della funzione, si possono trovare limiti inferiori e superiori per i valori di φ(n):

se p è un primo dispari maggiore di 13 e diverso da 19, 31, 43 e 61, (M. G. Monzingo, 1976);

φ(n) ≥ log₂n per n maggiore di 0 e diverso da 6;

Limite inferiore per il valore di φ(n) , per n > 2;

φ(n) > π(n), per n > 90;

Limite inferiore per il valore di φ(n) ;

Limite inferiore per il valore di φ(n) , per n > 2 e x > 6;

Limite inferiore per il valore di φ(n) , per n > 2 tranne che per 23# = 223092870 (J.B. Rosser e Lowell Schoenfeld, 1962), e quindi , per n > 2;

, per n diverso da 2 e 6 (D.G. Kendall e R. Osborn, 1965);

Limite inferiore per il valore di φ(n) , per n diverso da 1, 2, 3, 4, 6, 10, 12, 18 e 30 (Harold Shapiro, 1943);

Limite inferiore per il valore di φ(n) , per n > 42;

Limite inferiore per il valore di φ(n)^2 , per n > 1;

, per n composto (W. Sierpiński e A. Schinzel, 1988);

Limite superiore per il valore di φ(n)

φ(n)^k < φ(n^k), per n > 1;

φ(m)φ(n) ≤ φ(mn) ≤ mφ(n);

Limite inferiore e superiore per il valore di n / φ(n) , (Annapurna, 1938);

Limite superiore per il valore di φ(n * floor(σ(n) / n)) .

Se φ(n) = m, Limite superiore per il valore di n , dove il prodotto si calcola sui primi p tali che p – 1 divida m; se n è dispari, il limite superiore si dimezza (Hansraj Gupta, 1980).

Nel 1954 Andrzej Bobola Maria Schinzel e Wacław Franciszek Sierpiński (Varsavia, 14/3/1882 – Varsavia, 21/10/1969) dimostrarono che al variare di n i valori di φ(n + 1) / φ(n) sono densi tra i numeri reali positivi e i valori di φ(n + 1) / n sono densi nell’intervallo (0 .. 1).

Per d < 0.65, esistono infiniti valori di n tali che la funzione assume il valore n più di n^d volte.

φ(n) non assume mai valori delle seguenti forme:

dispari, tranne per φ(1) = φ(2) = 1;
2p^k, dove p è un primo della forma 3m + 1;
2p^2k, dove p è un primo della forma 3m + 2;
2p, se p è primo, ma 2p + 1 non lo è (ossia se p non è un primo di Sophie Germain).

La funzione assume invece come valore tutti i fattoriali.

Per n abbastanza grande il numero f(n) degli interi k non superiori a n per i quali φ(k) è un quadrato soddisfa Limiti inferiore e superiore per i valori di f(n) (W.D. Banks, J.B. Friedlander, Carl Pomerance e I.E. Shparlinski, 2004).

Il numero f(n) degli interi k non superiori a n per i quali φ(k) è rappresentabile come somma di due quadrati cresce come n / log(n)^(3 / 2) (W.D. Banks, Florian Luca, F. Saidak e I.E. Shparlinski, 2005);

La frazione degli interi per i quali φ(n) è rappresentabile come somma di tre quadrati tende a (Paul Pollack).

La tabella seguente mostra i valori di φ(n) per n fino a 20.

n	φ(n)
1	1
2	1
3	2
4	2
5	4
6	2
7	6
8	4
9	6
10	4
11	10
12	4
13	12
14	6
15	8
16	8
17	16
18	6
19	18
20	8

Se rφ(n) = φ(n + k) e tutti i primi che dividono m dividono sia n che n + k o non dividono nessuno dei due, rφ(mn) = φ(mn + mk).

Analogamente se φ(n) = rφ(n + k) e tutti i primi che dividono m dividono sia n che n + k o non dividono nessuno dei due, φ(mn) = rφ(mn + mk).

Sierpinski dimostrò nel 1956 che φ(n) = φ(n + k) ha almeno una soluzione per ogni k; non è però noto se, fissato k, le soluzioni siano infinite. Alcuni matematici (tra i quali Paul Erdös, Carl Pomerance e A. Sàrkozy) ritengono di sì per k = 1; A. Schinzel ritiene possibile che vi sia solo un numero finito di valori per k = 1, ma ritiene anche che per alcuni valori superiori di k esistano infinite soluzioni.

E’ noto che le soluzioni sono molto rare se k è un multiplo dispari di 3 (ossia se ha la forma 6m + 3); la tabella seguente mostra i casi inferiori a 10⁹ per k < 1000 (M. Fiorentini, 2017).

k	Valori di n
3	3, 5
9	9, 15
15	13, 15, 17, 21
21	21, 35
27	27, 45, 55
33	33, 39, 45, 55
39	37, 39, 45, 65, 105
45	39, 45, 51, 55, 63, 77
51	39, 51, 57, 63, 85, 95, 105
57	57, 75, 91, 95
63	61, 63, 105, 115
69	41, 51, 57, 69, 115, 175
75	65, 73, 75, 85, 105, 119
81	81, 135, 145, 165
87	87, 95, 99, 135, 145
93	61, 93, 135, 155, 195
99	91, 99, 117, 135, 165, 245
105	93, 105, 111, 117, 119, 143
111	97, 111, 117, 147, 175, 185, 195, 385
117	73, 111, 117, 135, 195, 315
123	111, 123, 205, 315
129	129, 215, 255, 275, 315, 455
135	117, 135, 153, 165, 175, 189, 231
141	89, 97, 111, 119, 123, 141, 187, 195, 203, 225, 231, 235, 315
147	147, 169, 205, 225, 245, 285
153	117, 153, 155, 171, 189, 209, 255, 285, 315, 455
159	111, 153, 157, 159, 265, 273, 285
165	129, 143, 165, 187, 195, 221, 231, 273
171	171, 225, 273, 285, 295, 325
177	113, 123, 177, 215, 259, 295, 305, 595
183	97, 153, 183, 273, 285, 305
189	183, 189, 203, 247, 315, 345, 385
195	155, 185, 193, 195, 205, 207, 221, 273, 287
201	201, 217, 287, 335, 665
207	123, 143, 153, 171, 207, 301, 345, 355, 525, 665
213	183, 187, 201, 213, 219, 355, 525
219	219, 231, 285, 357, 365, 525
225	195, 209, 219, 225, 255, 275, 315, 329, 357, 385
231	231, 253, 273, 315, 375, 385, 395, 425
237	153, 181, 219, 225, 237, 299, 395, 495, 595
243	243, 319, 365, 405, 435, 495
249	193, 219, 249, 319, 325, 399, 405, 415, 475, 495, 715
255	193, 221, 241, 255, 257, 261, 285, 315, 357, 371, 399
261	261, 285, 297, 323, 371, 405, 435, 445, 715
267	153, 183, 267, 273, 305, 357, 399, 445, 465, 525, 805
273	259, 273, 455, 465
279	183, 277, 279, 405, 425, 465, 585
285	219, 247, 267, 285, 287, 291, 323, 325, 399, 413, 455
291	291, 325, 445, 485, 585, 1155
297	273, 297, 351, 377, 405, 427, 495, 505, 665, 735
303	303, 351, 399, 429, 505, 515, 539, 585
309	309, 335, 429, 515, 555, 735, 1155
315	279, 305, 313, 315, 333, 351, 357, 385, 391, 429
321	219, 291, 321, 327, 333, 391, 403, 441, 483, 535, 545, 555, 1155
327	193, 219, 261, 327, 465, 469, 545, 585, 875
333	241, 287, 291, 333, 351, 441, 525, 555, 565, 585, 875, 1015, 1155
339	221, 327, 339, 475, 565, 715
345	285, 299, 305, 345, 391, 483, 497
351	219, 333, 337, 351, 405, 451, 585, 715, 945
357	233, 273, 281, 327, 339, 357, 399, 437, 451, 555, 595, 665
363	287, 313, 357, 363, 365, 369, 429, 495, 555, 565, 605, 945, 1085, 1365
369	241, 333, 369, 473, 615, 945
375	241, 325, 327, 365, 369, 375, 387, 425, 525, 595
381	277, 291, 381, 555, 635, 1365
387	387, 427, 645, 655, 765, 825, 945, 1365
393	381, 393, 405, 465, 475, 575, 655, 693, 765
399	397, 399, 407, 485, 525, 645, 665, 725, 765
405	323, 351, 405, 459, 469, 493, 495, 517, 525, 567, 693
411	219, 399, 403, 411, 423, 485, 493, 567, 675, 685, 725, 845, 1365
417	323, 337, 417, 459, 545, 695
423	257, 267, 291, 333, 357, 369, 421, 423, 561, 585, 609, 675, 693, 705, 945
429	281, 291, 313, 327, 353, 407, 417, 429, 459, 495, 715, 1155
435	377, 435, 465, 493, 495, 507, 609, 651
441	427, 441, 507, 615, 675, 735, 745, 805, 855
447	303, 337, 351, 407, 447, 507, 651, 745, 755, 1001, 1015, 1105
453	453, 459, 555, 755, 855
459	241, 351, 457, 459, 465, 513, 533, 567, 583, 627, 765, 855, 935, 945, 1225, 1365
465	305, 333, 403, 465, 477, 513, 525, 527, 551, 583, 637, 651
471	327, 429, 471, 477, 627, 685, 785, 975, 1365
477	313, 333, 349, 397, 459, 471, 477, 511, 545, 795, 819, 847, 855, 1925
483	287, 327, 357, 377, 471, 483, 489, 635, 735, 765, 805
489	291, 369, 489, 627, 663, 679, 815, 819, 875, 975
495	387, 429, 495, 505, 561, 585, 589, 663, 693, 707, 819
501	381, 401, 429, 437, 501, 611, 663, 707, 835, 975, 1085
507	481, 507, 585, 615, 721, 845, 1365
513	513, 675, 819, 833, 855, 885, 975, 1045, 1505
519	519, 545, 777, 865, 1785
525	421, 465, 511, 525, 555, 585, 595, 629, 715
531	339, 369, 531, 645, 671, 777, 885, 915, 1785
537	353, 449, 477, 489, 537, 549, 555, 651, 671, 679, 777, 895, 945
543	407, 471, 541, 543, 559, 833, 905, 1085, 1785
549	291, 451, 459, 549, 819, 855, 915, 1435
555	369, 433, 481, 485, 495, 543, 555, 585, 629, 735, 741, 777, 791
561	369, 429, 561, 627, 663, 693, 765, 915, 935, 1045, 1155
567	353, 549, 551, 567, 609, 637, 667, 689, 741, 775, 785, 945, 955, 1015, 1035, 1045, 1155
573	421, 461, 543, 573, 579, 621, 623, 645, 741, 915, 955, 965, 1035, 1225, 1365
579	511, 579, 675, 679, 765, 847, 965, 1025, 1645, 780825045
585	465, 555, 579, 585, 615, 621, 663, 697, 715, 737, 791, 819, 861, 931, 1001
591	577, 591, 603, 741, 777, 815, 985, 1025
597	597, 995, 1005, 1575, 1995
603	377, 433, 603, 651, 861, 1005, 1295, 1995
609	401, 481, 597, 609, 693, 713, 755, 945, 975, 1015, 1075
615	533, 555, 613, 615, 697, 731, 861
621	369, 409, 429, 459, 513, 527, 621, 695, 781, 903, 1035, 1065, 1225, 1265, 1575, 1995, 2275
627	627, 639, 675, 741, 777, 847, 855, 861, 889, 1001, 1045
633	459, 633, 637, 925, 1055, 1095, 1375, 1995
639	549, 561, 577, 603, 635, 639, 657, 775, 845, 1065, 1435, 1575
645	489, 521, 543, 559, 579, 597, 633, 645, 731, 803, 903, 1155
651	459, 651, 657, 945, 1005, 1015, 1085, 1095, 1365
657	421, 433, 657, 693, 707, 855, 1071, 1095, 1575, 1855
663	629, 661, 663, 689, 741, 765, 819, 903, 1045, 1105, 1235, 1785
669	561, 579, 669, 779, 915, 1115, 1175, 1995
675	585, 627, 657, 673, 675, 765, 825, 833, 875, 945, 987, 1071, 1155, 1309
681	369, 449, 459, 577, 609, 663, 681, 905, 925, 987, 1071, 1095, 1135, 1295, 2695
687	533, 687, 925, 1105, 1125, 1145, 1485
693	527, 671, 693, 759, 819, 945, 1125, 1155, 1165, 1185, 1265, 1275, 1615
699	401, 533, 651, 699, 785, 817, 855, 965, 1165, 1185, 1435, 1505, 1705
705	485, 527, 549, 555, 611, 615, 705, 777, 799, 897, 935, 987, 1015, 1071, 1155, 1463
711	449, 459, 543, 559, 657, 675, 697, 711, 815, 897, 1185, 1195, 1485, 1705, 1785, 418702574
717	617, 623, 699, 717, 791, 871, 1195, 1305
723	551, 627, 723, 861, 905, 1075, 1165, 1185, 1205
729	629, 729, 913, 957, 1095, 1215, 1305, 1485
735	651, 733, 735, 775, 777, 819, 833, 845, 891, 1001
741	601, 723, 741, 783, 851, 855, 975, 1043, 1095, 1215, 1235, 1995
747	579, 657, 747, 925, 957, 975, 995, 1197, 1205, 1215, 1245, 1425, 1445, 1485, 2145
753	549, 641, 723, 753, 995, 1071, 1255, 1615
759	543, 561, 627, 757, 759, 897, 969, 1035, 1197, 1265, 1305, 1325, 1547, 1925, 1995, 2275
765	579, 661, 663, 723, 765, 771, 783, 793, 855, 893, 923, 935, 945, 1045, 1071, 1085, 1113, 1197, 1309
771	741, 771, 1075, 1113, 1285, 1325, 1425
777	663, 679, 731, 777, 791, 819, 867, 969, 1095, 1295, 1365, 1395, 1625
783	769, 783, 803, 855, 891, 925, 949, 969, 979, 1113, 1215, 1305, 1315, 1335, 1495, 1595, 2145
789	521, 673, 789, 837, 899, 1005, 1023, 1315, 1425, 1547, 2415, 150345195
795	689, 755, 765, 785, 795, 901, 949, 1023, 1113, 1155, 1365
801	459, 549, 679, 801, 819, 915, 1071, 1197, 1335, 1395, 1575, 2415
807	543, 779, 801, 807, 915, 969, 1141, 1345, 1425, 1885, 2145
813	601, 661, 741, 793, 813, 973, 1355, 1995
819	511, 777, 793, 819, 943, 1365, 1395, 1495, 1595
825	645, 657, 715, 803, 825, 935, 975, 1105, 1155, 1169, 1309, 1365
831	629, 831, 871, 905, 1183, 1385, 1463, 1855, 2145, 2345, 2695
837	549, 731, 831, 837, 1055, 1215, 1235, 1275, 1395, 1705, 1755
843	543, 707, 777, 843, 1095, 1185, 1405, 1415, 1575, 1755, 2205, 2695
849	481, 579, 779, 849, 1001, 1065, 1415, 1455, 1855, 3185
855	641, 657, 741, 801, 855, 861, 873, 969, 975, 1003, 1045, 1197, 1211, 1239, 1365, 1463
861	579, 609, 701, 723, 771, 777, 813, 831, 843, 861, 903, 1003, 1067, 1435, 1455, 1755, 2035
867	533, 663, 763, 867, 969, 1007, 1071, 1405, 1445, 1575, 1615, 1785, 1885
873	527, 873, 975, 1335, 1455, 1755, 1771, 3465
879	577, 671, 741, 793, 873, 877, 879, 1465, 1525, 1729, 3185, 3465
885	767, 885, 915, 925, 975, 1003, 1067, 1225, 1239, 1253, 1287, 1295, 1547
891	629, 689, 819, 851, 891, 1037, 1053, 1131, 1215, 1281, 1285, 1485, 1515, 1525, 1595, 1995, 2205, 2485
897	433, 533, 593, 657, 663, 741, 851, 897, 1035, 1089, 1111, 1267, 1495, 2275, 2415
903	527, 577, 697, 873, 903, 909, 969, 1053, 1131, 1205, 1505, 1785, 1925
909	601, 673, 909, 1053, 1133, 1197, 1287, 1515, 1545, 1617, 1755, 2555
915	765, 793, 915, 927, 1037, 1099, 1113, 1281, 1365, 1617
921	921, 1095, 1125, 1535, 1545, 1705
927	703, 927, 1005, 1205, 1287, 1545, 1665, 2205, 3465
933	777, 803, 915, 921, 933, 1055, 1131, 1281, 1449, 1485, 1555, 1565, 1575, 1665, 2555
939	657, 861, 939, 965, 1355, 1449, 1565, 1617
945	837, 905, 915, 939, 945, 999, 1015, 1053, 1071, 1073, 1081, 1155, 1173, 1177, 1235, 1287
951	579, 673, 873, 951, 1221, 1281, 1323, 1425, 1585, 1665
957	737, 779, 829, 939, 957, 979, 999, 1045, 1131, 1305, 1351, 1485, 1595, 1635
963	657, 873, 963, 981, 999, 1173, 1209, 1323, 1355, 1449, 1565, 1605, 1635, 1665, 3465
969	741, 813, 861, 923, 939, 969, 1199, 1275, 1547, 1615, 1675, 1995
975	775, 925, 949, 965, 975, 981, 1025, 1035, 1105, 1221, 1365, 1407, 1435, 1547
981	579, 657, 713, 783, 981, 1395, 1407, 1635, 1755, 2135, 2275, 2625, 2765, 5005
987	623, 861, 987, 1027, 1157, 1209, 1309, 1575, 1645, 1655
993	673, 723, 801, 899, 943, 993, 1221, 1425, 1455, 1635, 1655, 2975, 3045
999	641, 723, 769, 861, 873, 997, 999, 1053, 1323, 1575, 1665, 1695, 1755, 2035, 2185, 2625, 3045, 3465

La tabella seguente riporta i valori di n per i quali φ(n) = φ(n + k), per n fino a 10000 e k fino a 20.

k	n
1	1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187
2	4, 7, 8, 10, 26, 32, 70, 74, 122, 146, 308, 314, 386, 512, 554, 572, 626, 635, 728, 794, 842, 910, 914, 1015, 1082, 1226, 1322, 1330, 1346, 1466, 1514, 1608, 1754, 1994, 2132, 2170, 2186, 2306, 2402, 2426, 2474, 2590, 2642, 2695, 2762, 2906, 3242, 3314, 3506, 3746, 3866, 3986, 4034, 4274, 4292, 4338, 4682, 4946, 5114, 5186, 5594, 5714, 5834, 5950, 6122, 6434, 6497, 6506, 6626, 6764, 7034, 7466, 8042, 8114, 8354, 8522, 8546, 8714, 8882, 9100, 9122, 9242, 9758, 9866
3	3, 5
4	8, 14, 16, 20, 35, 52, 64, 91, 140, 148, 244, 292, 403, 455, 616, 628, 772, 801, 1011, 1024, 1108, 1144, 1252, 1270, 1295, 1456, 1588, 1684, 1820, 1828, 2030, 2164, 2452, 2623, 2644, 2660, 2692, 2932, 3028, 3216, 3321, 3508, 3988, 4264, 4340, 4372, 4612, 4804, 4852, 4948, 5180, 5284, 5390, 5524, 5812, 6484, 6601, 6628, 7012, 7492, 7732, 7972, 8068, 8548, 8584, 8676, 8911, 9364, 9892
5	5, 9, 15, 21
6	24, 34, 36, 39, 43, 44, 57, 72, 78, 82, 84, 93, 96, 108, 111, 146, 178, 201, 216, 222, 225, 226, 228, 306, 327, 364, 366, 381, 399, 417, 432, 438, 442, 466, 471, 482, 516, 527, 540, 543, 562, 576, 597, 610, 626, 633, 648, 706, 714, 732, 738, 802, 818, 866, 898, 912, 921, 924, 942, 948, 972, 1011, 1042, 1137, 1152, 1158, 1186, 1202, 1227, 1281, 1308, 1461, 1497, 1522, 1536, 1538, 1602, 1606, 1623, 1662, 1713, 1716, 1731, 1742, 1746, 1763, 1812, 1858, 1878, 1893, 1905, 1906, 1956, 2098, 2150, 2184, 2253, 2257, 2258, 2307, 2361, 2382, 2425, 2433, 2466, 2487, 2498, 2516, 2526, 2592, 2631, 2642, 2676, 2742, 2757, 2811, 2818, 2866, 2916, 2973, 2978, 3027, 3106, 3117, 3162, 3202, 3233, 3246, 3252, 3270, 3351, 3442, 3456, 3506, 3549, 3603, 3678, 3690, 3826, 3873, 3891, 3966, 3981, 3986, 4038, 4143, 4162, 4178, 4188, 4197, 4212, 4322, 4338, 4377, 4398, 4413, 4542, 4546, 4562, 4608, 4626, 4701, 4706, 4752, 4786, 4863, 4946, 4953, 5007, 5042, 5052, 5058, 5218, 5232, 5262, 5266, 5268, 5277, 5331, 5378, 5403, 5458, 5542, 5544, 5602, 5666, 5906, 5938, 5982, 6002, 6051, 6082, 6087, 6096, 6178, 6276, 6396, 6537, 6558, 6626, 6753, 6807, 6843, 6866, 6887, 6898, 6912, 6918, 7058, 7167, 7206, 7212, 7278, 7346, 7356, 7362, 7401, 7422, 7522, 7572, 7671, 7762, 7776, 7803, 7858, 7926, 7941, 7977, 8076, 8082, 8098, 8145, 8146, 8157, 8193, 8258, 8286, 8292, 8306, 8402, 8482, 8546, 8571, 8718, 8730, 8748, 8818, 8913, 9026, 9111, 9183, 9298, 9442, 9543, 9561, 9602, 9726, 9732, 9777, 9778, 9813, 9921, 9942, 9986
7	5, 7, 21, 45, 75, 105, 285, 488, 585, 765, 1148, 1275, 1358, 1785, 2528, 3465, 4088, 6825, 9405
8	13, 16, 19, 25, 28, 32, 40, 70, 104, 128, 175, 182, 209, 280, 296, 488, 551, 584, 657, 715, 806, 910, 1232, 1256, 1544, 1602, 2022, 2048, 2216, 2288, 2504, 2540, 2590, 2717, 2912, 3176, 3368, 3640, 3656, 4060, 4328, 4904, 5246, 5288, 5320, 5384, 5864, 5969, 6056, 6432, 6475, 6642, 7016, 7587, 7739, 7976, 8105, 8528, 8680, 8744, 9224, 9608, 9704, 9896
9	9, 15
10	20, 26, 35, 100, 130, 160, 370, 400, 610, 730, 793, 1000, 1570, 1843, 1930, 2500, 2560, 2770, 2860, 3130, 3970, 4000, 4171, 4210, 4570, 5410, 5767, 6130, 6400, 6610, 6730, 7330, 7570, 8770, 9106, 9640, 9970, 9991
11	7, 11, 27, 33, 45, 63, 135, 165, 285, 304, 345, 765, 855, 964, 1144, 1575, 1744, 2134, 2295, 2805, 6424, 6604
12	48, 68, 72, 78, 86, 88, 114, 143, 144, 156, 157, 164, 168, 186, 192, 203, 216, 222, 247, 273, 292, 356, 402, 432, 444, 450, 452, 456, 612, 654, 728, 732, 762, 798, 834, 864, 876, 884, 932, 942, 964, 1032, 1054, 1080, 1086, 1124, 1147, 1152, 1194, 1209, 1220, 1252, 1266, 1296, 1412, 1428, 1464, 1476, 1604, 1636, 1679, 1732, 1796, 1824, 1842, 1848, 1884, 1896, 1944, 2022, 2084, 2147, 2274, 2279, 2304, 2316, 2372, 2375, 2404, 2445, 2454, 2562, 2616, 2705, 2747, 2922, 2994, 3044, 3072, 3076, 3204, 3212, 3246, 3324, 3426, 3432, 3462, 3484, 3492, 3526, 3624, 3716, 3756, 3786, 3810, 3812, 3912, 4196, 4300, 4331, 4368, 4506, 4514, 4516, 4614, 4687, 4722, 4764, 4850, 4866, 4932, 4974, 4996, 5032, 5049, 5052, 5184, 5262, 5284, 5352, 5484, 5514, 5622, 5636, 5732, 5832, 5946, 5956, 6054, 6107, 6212, 6234, 6324, 6404, 6466, 6492, 6504, 6540, 6702, 6884, 6912, 7012, 7098, 7206, 7356, 7367, 7380, 7652, 7746, 7782, 7835, 7869, 7932, 7962, 7972, 7979, 7991, 8076, 8286, 8324, 8356, 8376, 8394, 8424, 8644, 8676, 8754, 8796, 8826, 9084, 9092, 9124, 9167, 9216, 9252, 9402, 9412, 9504, 9572, 9726, 9892, 9906
13	13, 39, 51, 63, 75, 135, 195, 231, 482, 2132, 2295, 3315, 4712, 6435
14	16, 28, 34, 41, 56, 70, 130, 194, 224, 392, 482, 518, 674, 779, 854, 1022, 1154, 1394, 1538, 1568, 2018, 2198, 2402, 2498, 2594, 2702, 2744, 2924, 2993, 3554, 3584, 3878, 4322, 4382, 5018, 5378, 5420, 5558, 5894, 6272, 6338, 6398, 6683, 6722, 6914, 7394, 7574, 7778, 8354, 8582, 9122, 9254, 9422, 9563, 9602
15	13, 15, 17, 21
16	26, 32, 38, 50, 56, 61, 64, 77, 80, 95, 140, 208, 245, 256, 350, 364, 369, 418, 560, 579, 592, 976, 1102, 1168, 1314, 1333, 1430, 1612, 1820, 2464, 2512, 3088, 3204, 3289, 4044, 4096, 4432, 4453, 4576, 4975, 5008, 5080, 5180, 5409, 5434, 5824, 6352, 6736, 7280, 7312, 8120, 8656, 9065, 9577, 9808
17	17, 33, 35, 39, 51, 57, 135, 231, 255, 435, 465, 808, 855, 945, 975, 1558, 1768, 2788, 3298, 3675, 5296, 8415, 9928
18	52, 72, 73, 82, 102, 108, 112, 117, 129, 132, 171, 187, 216, 234, 246, 252, 279, 287, 288, 324, 333, 438, 534, 603, 648, 666, 675, 678, 684, 836, 918, 952, 981, 1092, 1098, 1139, 1143, 1189, 1197, 1251, 1296, 1314, 1326, 1398, 1413, 1446, 1548, 1581, 1620, 1629, 1686, 1728, 1791, 1830, 1878, 1899, 1944, 2118, 2142, 2196, 2214, 2299, 2406, 2454, 2581, 2598, 2600, 2686, 2694, 2736, 2763, 2772, 2826, 2844, 2911, 2916, 3033, 3126, 3411, 3456, 3474, 3558, 3606, 3681, 3843, 3924, 4246, 4383, 4491, 4566, 4608, 4614, 4806, 4818, 4862, 4869, 4986, 5139, 5148, 5193, 5226, 5238, 5289, 5353, 5436, 5574, 5634, 5679, 5715, 5718, 5868, 6294, 6450, 6552, 6759, 6771, 6774, 6921, 7083, 7146, 7174, 7275, 7299, 7398, 7461, 7494, 7548, 7578, 7776, 7893, 7926, 7936, 8028, 8226, 8271, 8308, 8433, 8454, 8598, 8748, 8919, 8934, 9081, 9158, 9318, 9351, 9486, 9606, 9699, 9738, 9756, 9810
19	19, 25, 57, 225, 273, 285, 296, 735, 1976, 3116, 3686, 4706, 4845, 5115, 6405, 7076, 9009, 9405
20	37, 40, 52, 55, 70, 91, 155, 200, 260, 305, 320, 407, 740, 755, 800, 851, 905, 1007, 1055, 1220, 1241, 1460, 1586, 1655, 2000, 2015, 2705, 3140, 3155, 3455, 3686, 3755, 3860, 4055, 4847, 4955, 5000, 5120, 5123, 5255, 5540, 5720, 6005, 6260, 6731, 6905, 7655, 7940, 8000, 8342, 8420, 8705, 9140, 9155, 9275, 9305

Qui trovate gli interi n minori di 10¹² tali che φ(n) = φ(n + 1) (T.D. Noe e Jud McCranie, The Online Encyclopedia of Integer Sequences http://oeis.org).

Maiakowsky dimostrò nel 1974 che 2φ(n) = φ(n + k) ha almeno una soluzione per ogni intero k maggiore di zero.

La tabella seguente riporta i valori di n per i quali 2φ(n) = φ(n + k), per n fino a 10000 e k fino a 20.

k	n
1	2, 4, 16, 154, 256, 286, 364, 804, 1066, 2146, 3382, 4550, 6106, 7700, 8176, 9268
2	1, 2, 3, 6, 15, 30, 255, 510, 525, 990, 1950, 2520, 5250, 6510, 7410
3	1, 12, 18, 22, 36, 42, 48, 54, 108, 114, 182, 216, 258, 270, 288, 324, 366, 456, 462, 474, 486, 576, 654, 768, 858, 906, 978, 1092, 1258, 1296, 1338, 1458, 1626, 1728, 2094, 2106, 2304, 2376, 2526, 2616, 2634, 2772, 3048, 3138, 3198, 3456, 3606, 3678, 3786, 3888, 4038, 4146, 4374, 4866, 5118, 5246, 5450, 5514, 5946, 6054, 6306, 6344, 6378, 6438, 6504, 6918, 7278, 7386, 7674, 7776, 7926, 8110, 8574, 8748, 9096, 9186, 9294, 9528, 9978
4	2, 4, 6, 9, 12, 30, 60, 510, 765, 945, 1020, 1050, 1980, 3003, 3900, 5040
5	1, 3, 10, 50, 80, 200, 500, 1250, 1280, 1430, 2000, 3200, 4820, 5330, 5624, 8000, 8036, 8420
6	4, 6, 7, 10
7	3, 8, 14, 28, 112, 196, 784, 1372, 1462, 1792, 2710, 3136, 5332, 7462, 8614, 9604
8	4, 8, 12, 18, 24, 33, 60, 120, 315, 345, 525, 1020, 1530, 1890, 2040, 2100, 3960, 6006, 7800, 7905
9	3, 26, 36, 54, 56, 66, 108, 126, 144, 162, 324, 342, 418, 476, 546, 648, 774, 810, 864, 972, 1098, 1300, 1368, 1386, 1422, 1458, 1728, 1962, 2304, 2574, 2718, 2934, 3276, 3774, 3888, 3968, 4014, 4154, 4374, 4878, 5184, 5762, 6282, 6318, 6912, 7128, 7154, 7578, 7848, 7902, 8316, 8440, 9144, 9414, 9594, 9694
10	5, 10, 18, 24, 27, 30, 42, 63, 231
11	5, 22, 28, 40, 44, 158, 176, 242, 280, 444, 654, 968, 1406, 2816, 3440, 3872, 4004, 4644, 5064, 8844, 8906, 9128
12	8, 9, 12, 14, 20
13	26, 52, 110, 140, 208, 322, 372, 532, 582, 676, 952, 1054, 2002, 2146, 3328, 5180, 5206, 6106, 7092, 7954, 7960, 8788
14	7, 10, 11, 14, 20, 21, 42, 90, 105, 150, 180, 210, 435, 570, 1140, 1170, 1530, 1785, 2550, 3570, 4455, 6930
15	5, 62, 76, 90, 104, 150, 180, 240, 270, 274, 310, 410, 444, 450, 540, 570, 600, 700, 710, 900, 1010, 1080, 1290, 1310, 1440, 1500, 1510, 1584, 1620, 1672, 1810, 1830, 1872, 1956, 2108, 2250, 2280, 2370, 2388, 2410, 2430, 2510, 2700, 2710, 2810, 2880, 3270, 3600, 3684, 3692, 3750, 3840, 4050, 4290, 4310, 4530, 4890, 4910, 5196, 5612, 5710, 6000, 6010, 6276, 6290, 6410, 6480, 6492, 6690, 6910, 6924, 7010, 7290, 7572, 8060, 8100, 8130, 8400, 8640, 8810, 9000, 9084, 9254, 9600, 9710, 9910
16	8, 16, 24, 25, 36, 48, 57, 66, 120, 225, 240, 630, 690, 1050, 2040, 3060, 3780, 4080, 4125, 4200, 7920
17	9, 15, 28, 34, 68, 74, 308, 438, 494, 648, 1634, 2312, 2618, 3010, 3116, 4352, 4862, 5058, 6188, 7578, 8470
18	12, 16, 18, 19, 21, 30
19	5, 7, 9, 15, 26, 32, 38, 76, 124, 196, 286, 304, 350, 366, 560, 576, 1666, 2926, 4588, 4864, 5434, 6832, 6916, 7240, 7384
20	10, 20, 36, 45, 48, 54, 60, 69, 84, 126, 462

In particolare se p = 2^{2^q} – 1 è un primo di Fermat, 2φ(p – 1) = 2(2^{q – 1}) = 2^q = p – 1 = φ(p).

Vi sono interi n tali che kφ(n) = φ(n + 1) con k > 1.

La tabella seguente riporta i valori di n fino a 10000 tali che 2φ(n) = φ(n + 1).

n	φ(n)
2	1
4	2
16	8
154	60
256	128
286	120
364	144
804	264
1066	480
2146	1008
3382	1584
4550	1440
6106	2940
7700	2400
8176	3456
9268	3960

La tabella seguente riporta i valori di n fino a 10000 tali che 3φ(n) = φ(n + 1).

n	φ(n)
6	2
12	4
18	6
36	12
72	24
90	24
96	32
108	36
162	54
192	64
432	144
486	162
576	192
702	216
768	256
792	240
924	240
1152	384
1296	432
1458	486
2592	864
2916	972
3456	1152
3888	1296
4698	1512
5550	1440
6696	2160
7998	2520
8700	2240

La tabella seguente riporta i valori di n fino a 10⁶ tali che 4φ(n) = φ(n + 1).

n	φ(n)
1260	288
13650	2880
17556	4320
18720	4608
24510	6048
42120	10368
113610	25920
244530	51840
266070	60480
712080	177408
749910	171360
795690	181440
992250	226800

La tabella seguente riporta i valori di n fino a 10⁹ tali che 5φ(n) = φ(n + 1).

n	φ(n)
11242770	2246400
18673200	3732480
77805000	15552000
117138840	23224320
122649450	24192000
278023200	54743040
393513120	75479040
881879460	175633920

Vi sono interi n tali che φ(n) = kφ(n + 1) con k > 1.

In particolare, se p e 2p – 1 sono primi (e secondo la congettura di Dickson vi sarebbero infiniti casi), φ(2p – 1) = 2p – 2 = 2φ(2p), esistono però vari altri valori di n tali che φ(n) = 2φ(n + 1).

La tabella seguente riporta i valori di n fino a 1000 tali che φ(n) = 2φ(n + 1).

n	φ(n)
5	4
13	12
35	24
37	36
61	60
73	72
157	156
193	192
277	276
313	312
397	396
421	420
455	288
457	456
541	540
613	612
661	660
665	432
673	672
733	732
757	756
877	876
997	996

La tabella seguente riporta i valori di n fino a 10⁵ tali che φ(n) = 3φ(n + 1).

n	φ(n)
119	96
527	480
545	432
2849	2160
3689	2880
4487	3840
6649	6480
18619	18144
26771	25344
30377	29520
44659	40320
47585	36720
50507	47520
76997	74880
83021	81600

La tabella seguente riporta i valori di n fino a 10⁶ tali che φ(n) = 4φ(n + 1).

n	φ(n)
629	576
1469	1344
85139	80640
100889	100224
139859	124416
154979	138240
168149	167040
304079	276480
396899	362880
838199	806400

La tabella seguente riporta i valori di n fino a 10⁹ tali che φ(n) = 5φ(n + 1).

n	φ(n)
17907119	16588800
18828809	17107200
31692569	31000320
73421039	73113600
179467469	178053120
322757819	319334400
337567229	323481600
627702389	623185920
975314339	935193600

D.J. Newman dimostrò che deve esistere almeno una soluzione della diseguaglianza φ(30n) > φ(30n + 1), ma la ricerca sino a 20 milioni non permise di trovarne una. Poi Greg Martin trovò il minimo esempio: un numero di 1120 cifre!

Esistono sequenze di interi consecutivi tali che φ(n) abbia valori crescenti, tali cioè che φ(n) < φ(n + 1) < φ(n + 2) ecc., tuttavia tali sequenze sono in genere molto brevi e non se ne conosce nessuna di 5 o più interi; se esiste, il termine minimo è maggiore di 10⁹ (M. Fiorentini, 2015).

La tabella seguente mostra il minimo valore di n a partire dal quale si trovi una sequenza di lunghezza k.

k	n
1	1
2	2
3	105
4	1484

Esistono sequenze di interi consecutivi tali che φ(n) abbia valori decrescenti, tali cioè che φ(n) > φ(n + 1) > φ(n + 2) ecc., tuttavia tali sequenze sono in genere molto brevi e non se ne conosce nessuna di 5 o più interi; se esiste, il termine minimo è maggiore di 10⁹ (M. Fiorentini, 2015).

La tabella seguente mostra il minimo valore di n a partire dal quale si trovi una sequenza di lunghezza k.

k	n
1	1
2	5
3	313
4	823

Se chiamiamo a(m) il numero di interi per i quali φ(n) = m, otteniamo una funzione piuttosto irregolare; per esempio, a(1438) = 2, a(1440) = 72, a(1442) = a(1444) = 0.

In ogni caso a(m) è un numero finito, ossia, fissato m, esiste al massimo un numero finito di interi n tali che φ(n) = m.

I pochi risultati generali sono:

a(1) = 2 e a(m) = 0 per m dispari e maggiore di 1;
a(4m + 2) è 0, 2 o 4 (V.L. Klee, 1946).

Inoltre Limite che coinvolge la funzione a(n) (Dressler, 1970).

I numeri pari per i quali a(n) = 0 sono i numeri non tozienti.

La tabella seguente mostra i valori di a(n), per n uguale a 1 e pari fino a 20.

n	a(n)
1	2
2	3
4	4
6	4
8	5
10	2
12	6
14	0
16	6
18	4
20	5

I numeri pari per i quali a(n) = 0 sono i numeri non tozienti.

La tabella seguente mostra i valori di n fino a 1000 per ogni valore di a(n).

a(n)	n
0	14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202, 206, 214, 218, 230, 234, 236, 242, 244, 246, 248, 254, 258, 266, 274, 278, 284, 286, 290, 298, 302, 304, 308, 314, 318, 322, 326, 334, 338, 340, 350, 354, 362, 364, 370, 374, 376, 386, 390, 394, 398, 402, 404, 406, 410, 412, 414, 422, 426, 428, 434, 436, 446, 450, 454, 458, 470, 472, 474, 482, 484, 488, 494, 496, 510, 514, 516, 518, 526, 530, 532, 534, 538, 542, 548, 550, 554, 558, 566, 572, 574, 578, 582, 590, 594, 596, 602, 604, 608, 610, 614, 622, 626, 628, 634, 638, 644, 650, 654, 662, 666, 668, 670, 674, 678, 680, 686, 694, 698, 702, 706, 710, 714, 722, 724, 728, 730, 734, 740, 746, 748, 752, 754, 758, 762, 766, 770, 774, 778, 782, 788, 790, 794, 798, 802, 804, 806, 814, 818, 824, 830, 834, 842, 844, 846, 850, 854, 866, 868, 870, 872, 874, 878, 890, 892, 894, 898, 902, 908, 914, 916, 922, 926, 934, 938, 942, 944, 948, 950, 954, 958, 962, 964, 968, 974, 978, 986, 988, 992, 994, 998
2	2, 10, 22, 28, 30, 46, 52, 54, 58, 66, 70, 78, 82, 102, 106, 110, 126, 130, 136, 138, 148, 150, 166, 172, 178, 190, 196, 198, 210, 222, 226, 228, 238, 250, 262, 268, 270, 282, 292, 294, 306, 310, 316, 330, 342, 346, 358, 366, 372, 378, 382, 388, 418, 430, 438, 442, 462, 466, 478, 490, 498, 502, 506, 508, 522, 546, 556, 562, 568, 570, 580, 586, 598, 606, 618, 630, 642, 646, 652, 658, 676, 682, 690, 708, 718, 726, 738, 742, 750, 772, 786, 796, 808, 810, 812, 822, 826, 838, 852, 856, 858, 862, 882, 886, 906, 910, 918, 930, 940, 946, 966, 970, 976, 982, 990
3	2, 44, 56, 92, 104, 116, 140, 164, 204, 212, 260, 296, 332, 344, 356, 380, 392, 444, 452, 476, 524, 536, 564, 584, 588, 620, 632, 684, 692, 716, 744, 764, 776, 836, 860, 884, 932, 956, 980
4	4, 6, 18, 42, 100, 162, 184, 208, 328, 424, 460, 468, 486, 492, 616, 636, 664, 688, 700, 712, 784, 820, 900, 904
5	8, 20, 220, 272, 300, 368, 416, 456, 500, 656, 732, 848, 876
6	12, 16, 84, 88, 112, 232, 348, 408, 592, 736, 760, 780, 832, 952, 984
7	32, 132, 156, 544, 912, 924
8	36, 64, 176, 200, 224, 280, 324, 464, 520, 888, 920
9	40, 60, 108, 128, 252, 276, 440, 612, 696, 996
10	24, 80, 180, 256, 264, 828
11	48, 512, 540
12	160, 168, 352, 448, 816, 928, 972
13	396, 400, 420, 552, 560, 660
15	704, 896
16	312, 320
17	72, 96, 120, 504, 756, 800
18	336, 880
19	216, 528
20	936
21	144, 192, 600, 640, 648, 792
22	624
25	360, 840
27	384
28	288
31	240, 672
32	768
34	432
37	480
38	576
45	864
49	720, 960

Gli unici interi per i quali φ(n) = Π(n)² sono: 1, 8, 108, 250, 6174, 41154 (J.M. De Koninck e A. Mercier, 2004).

Per i legami con la funzione σ v. funzione σ.

Tabelle numeriche

I valori di φ(n) per n fino a 1000,
I valori di n per i quali φ(n) = φ(n + k), per n fino a 10⁶ e k fino a 100,
I valori di n per i quali 2φ(n) = φ(n + k), per n fino a 10⁶ e k fino a 100,
Il minimo valore di n per il quale 2φ(n) = φ(n + k), per k da 1 a 1000,
I valori di n fino a 10⁹ tali che 2φ(n) = φ(n + 1),
I valori di n fino a 10⁹ tali che 3φ(n) = φ(n + 1),
I valori di n fino a 10⁹ tali che 4φ(n) = φ(n + 1),
I valori di n fino a 10⁶ tali che φ(n) = 2φ(n + 1),
I valori di n fino a 10⁹ tali che φ(n) = 3φ(n + 1),
I valori di n fino a 10⁹ tali che φ(n) = 4φ(n + 1),
I valori di a(n), per n uguale a 1 e pari fino a 1000,
I valori di n fino a 10000 per ogni valore di a(n),
Il minimo intero n e la differenza d tra termini consecutivi delle progressioni aritmetiche di tre interi con lo stesso valore di φ, per n fino a 10⁶ e d fino a 1000,
Il minimo intero n e la differenza d tra termini consecutivi delle progressioni aritmetiche di quattro interi con lo stesso valore di φ, per n fino a 10⁶ e d fino a 1000,
I valori di w(n), per n fino a 1000,
I minimi interi per i quali il valore di w(n) sia uguale a k, per k fino a 1000 .

Vedi anche

Congetture sulla Funzione φ(n), Costante del toziente, Funzione φ, Funzione φ*, Funzione φ#, Funzione φ_k, Numeri non cotozienti, Numeri non tozienti.

Bibliografia

Adler, Andrew; Coury, John E.; The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
De Koninck, Jean-Marie; Those Fascinating Numbers, American Mathematical Society, 2009 -
Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.
Roberts, Joe; The Lure of the Integers, The Mathematical Association of America, 1992 -
Una miniera di informazioni sugli interi.
Stanley, Richard P.; Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
Surányi, János; Topics in the Theory of Numbers, Springer, 2003.
Wells, David; Prime Numbers, John Wiley & Sons, 2005 -
Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.

← φ φ*(n) →