Don't take life too seriously: it's just a temporary situation

Insiemi debolmente liberi da triple (costante degli)

Matematica combinatoria 

La definizione della costante degli insiemi debolmente liberi da triple nasce dalla ricerca di insiemi di numeri naturali con alcune caratteristiche; in particolare, si cerca di costruire un insieme di numeri naturali maggiori di zero e non superiori a un limite fissato n, in modo che gli elementi dell’insieme rispettino certi vincoli e che l’insieme contenga il massimo numero di elementi p(n).

Per ogni specifico vincolo sugli elementi dell’insieme si cerca poi Limite della densità dei numeri appartenenti all'insieme, ossia il limite cui tende il rapporto tra i numeri che si possono mettere nell’insieme e n. Notate che quando si passa da n a n + 1 si può costruire un insieme completamente diverso, senza necessariamente includere gli elementi dell’insieme precedente.

Per esempio, possiamo stabilire come vincolo che se l’insieme contiene un numero, non deve contenere il suo doppio. In questo caso possiamo costruire l’insieme con tutti i numeri dispari non superiori a n, raggiungendo una densità pari a Un mezzo, ma si può far di meglio: nel caso n = 12, p(n) = 8, come dimostra l’insieme { 1 3 4 5 7 9 11 12 }. In questo caso p(n) si calcola con la ricorrenza Ricorrenza per il calcolo di p(n), iniziando con p(0) = 0, e il limite è Limite cui tende p(n).

 

In generale se il vincolo è che è sia vietato includere nell’insieme sia un numero m, sia  un suo multiplo km, con k fissato, un insieme col massimo numero di elementi si può costruire escludendo solo i numeri divisibili al massimo per potenze con esponente dispari di k, ma non per potenze superiori. Nel caso di k = 2 si escludono i numeri divisibili per 2, 8, 32..., ma non per potenze superiori di 2. In questo caso l’insieme limite è Limite cui tende p(n) / n.

 

Basta però rendere appena più complicato il vincolo, per trovarsi un problema inaspettatamente complesso: che succede, infatti, se chiediamo che l’insieme non contenga sia il doppio che il triplo di ogni numero contenuto? Il vincolo richiede semplicemente che la terna m, 2m, 3m non sia contenuta nell’insieme in questo caso l’insieme si dice “debolmente libero da triple”. Per n = 12 un insieme col massimo numero di elementi è costituito da { 1, 3, 4, 5, 7, 8, 9, 10, 11 }, quindi p(12) = 9.

 

La tabella seguente riporta il valore di p(n) per n fino a 70 (Steven Finch, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

p(n)

1

1

2

2

3

2

4

3

5

4

6

5

7

6

8

7

9

7

10

8

11

9

12

10

13

11

14

12

15

12

16

13

17

14

18

14

19

15

20

16

21

16

22

17

23

18

24

19

25

20

26

21

27

21

28

22

29

23

30

24

31

25

32

26

33

26

34

27

35

28

36

29

37

30

38

31

39

31

40

32

41

33

42

34

43

35

44

36

45

36

46

37

47

38

48

39

49

40

50

41

51

41

52

42

53

43

54

43

55

44

56

45

57

45

58

46

59

47

60

48

61

49

62

50

63

50

64

51

65

52

66

53

67

54

68

55

69

55

70

56

 

Il limite cui tende il rapporto p(n) / n è compreso tra 0.8000085476 e 0.800961, ma il valore esatto, detto “costante degli insiemi debolmente liberi da triple”, non è noto.

Contattami

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