-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathaliquot.qmd
173 lines (143 loc) · 4.82 KB
/
aliquot.qmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
---
title: "A sequência alíquota"
number-sections: true
lang: pt-BR
---
## A função alíquota
:::{.problem}
Seja $n\in\mathbb N_0$. Denote por $\sigma(n)$ a soma dos divisores de $n$ entre $1$ e $n-1$ (ou seja, $n$ está desconsiderado). Em outras palavras,
$$
\sigma(n)=\sum_{d\mid n,\ d<n}d.
$$
Por exemplo
$$
\sigma(8)=1+2+4=7
$$
e
$$
\sigma(24)=1+2+3+4+6+8+12=36.
$$
Nós definimos também
$$
\sigma(1)=\sigma(0)=0.
$$
Neste projeto vamos explorar quais tipos de sequências obtemos por sucessivamente aplicar a função $\sigma$ em um número natural.
:::
## Tarefa 1
:::{.subproblem}
Escreva uma função `sum_divisors( n )` em `GAP` que dado um numero `n` devolve $\sigma(n)$. A sua função deve se comportar como no seguinte exemplo.
```matlab
gap> sum_divisors( 8 );
7
gap> sum_divisors( 9 );
4
gap> sum_divisors( 11 );
1
```
:::
:::{.hint}
Pode usar as funções `DivisorsInt` ([manual](https://docs.gap-system.org/doc/ref/chap14.html#X809E0E1B83AF7695)) e `Sum` ([manual](https://docs.gap-system.org/doc/ref/chap14.html#X809E0E1B83AF7695)). Também pode precisar de `if` para decidir se `n=0`, pois `DivisorsInt( 0 )` não funciona (@sec-if).
:::
## Tarefa 2
:::{.subproblem}
Um número $n$ chama-se *perfeito* se $\sigma(n)=n$.
1. Escreva uma função `is_perfect( n )` que devolva `true` se `n` é perfeito e `false` se `n` não é perfeito.
```matlab
gap> is_perfect( 6 );
true
gap> is_perfect( 20 );
false
gap> is_perfect( 28 );
true
```
1. Ache todos os números perfeitos entre `1` e `1000000`.
2. Um número $n$ chama-se *abundante*, se $\sigma(n)>n$. Escreva uma função `is_abundant( n )` que devolve `true` se o número `n` é abundante e `false` se não é abundante.
3. Ache todos os números abundantes entre `1` e `1000`.
:::
:::{.hint}
Use a funução `sum_divisors` escrita para a tarefa anterior. Se precisar, revise como trabalhar com valores booleanas (@sec-bool).
:::
## Tarefa 3
:::{.subproblem}
Dois números $n$ e $m$ são chamados de amigáveis se $\sigma(n)=m$ e $\sigma(m)=n$.
1. Escreva uma função `is_friendly( n )` que verifica se um número `n` é membro de um par amigável. A função deve devolver o par de `n` caso sim, e `0` caso não.
```matlab
gap> is_friendly( 6 );
6
gap> is_friendly( 220 );
284
gap> is_friendly( 284 );
220
gap> is_friendly( 200 );
0
```
2. Ache todos os pares amigáveis de números entre `1` e `1000000`.
:::
:::{.hint}
Use a função `sum_divisors` escrita para Tarefa 1. Pode usar também a função `Filtered` sobre `[1..1000000]`
(@sec-list).
:::
<!--
is_friendly := function( n )
local n1;
n1 := sigma( n );
return n <> n1 and sigma( n1 ) = n;
end;
-->
## Tarefa 4
:::{.subproblem}
Seja $a_0\in\mathbb N$ arbitrário. Defina a sequência que começa por $a_0$ e para $i\geq 1$, $a_i=\sigma(a_{i-1})$. Por exemplo, se $a_0=8$, então
$$
a_0=8,\quad a_1=\sigma(8)=7,\quad a_2=\sigma(7)=1, a_3=\sigma(1)=0, \quad a_4=\sigma(0)=0.
$$
Este tipo de sequência chama-se [sequência alíquota](https://en.wikipedia.org/wiki/Aliquot_sequence) (aliquot sequence).
1. Escreva uma função `aliquot_sequence( a0, k )` que, dado `a0` e um número `k`, devolve os primeiros `k` termos da sequência alíquota que inicia-se com `a0`.
```matlab
gap> aliquot_sequence( 8, 4 );
[ 8, 7, 1, 0 ]
gap> aliquot_sequence( 24, 6 );
[ 24, 36, 55, 17, 1, 0 ]
gap> aliquot_sequence( 30, 15 );
[ 30, 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1 ]
```
1. Modifique a sua função em tal forma que a execução termina assim que a sequẽncia vira periódica.
```matlab
gap> aliquot_sequence_until_repeat( 21 );
[ 21, 11, 1, 0, 0 ]
gap> aliquot_sequence_until_repeat( 42 );
[ 42, 54, 66, 78, 90, 144, 259, 45, 33, 15, 9, 4, 3, 1, 0, 0 ]
gap> aliquot_sequence_until_repeat( 34 );
[ 34, 20, 22, 14, 10, 8, 7, 1, 0, 0 ]
```
1. O comprimento da sequência é o número de passos que precisamos fazer até a sequência vira periódica. Ache números entre $1$ e $1000$ que produzem o sequência particularmente longas.
:::
:::{.hint}
Além de utulizar a função `sum_divisors`, vai precisar de listas (@sec-list), variáveis locais (@sec-functions), e laços (@sec-for e @sec-while). Pode precisar também a expressão `break` (@sec-break-continue).
:::
Este projeto foi inspirado pelo seguinte vídeo.
{{< video https://youtu.be/OtYKDzXwDEE?si=ye9hrQC-TjHL9W5y width="560" height="315" >}}
<!--
aliquot_sequence := function( a0, k )
local i, seq;
seq := [a0];
for i in [1..k-1] do
Add( seq, sum_divisors( seq[i] ));
od;
return seq;
end;
aliquot_sequence_until_repeat := function( a0 )
local i, seq, next_term;
seq := [a0];
i := 1;
while true do
next_term := sum_divisors( seq[i] );
if next_term in seq then
Add( seq, next_term );
break;
fi;
Add( seq, next_term );
i := i + 1;
od;
return seq;
end;
-->