8  A sequência alíquota

8.1 A função alíquota

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.

8.2 Tarefa 1

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.

gap> sum_divisors( 8 );
7
gap> sum_divisors( 9 );
4
gap> sum_divisors( 11 );
1

Pode usar as funções DivisorsInt (manual) e Sum (manual). Também pode precisar de if para decidir se n=0, pois DivisorsInt( 0 ) não funciona (Seção 5.1).

8.3 Tarefa 2

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.
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.

Use a funução sum_divisors escrita para a tarefa anterior. Se precisar, revise como trabalhar com valores booleanas (Seção 2.2).

8.4 Tarefa 3

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.
gap> is_friendly( 6 );
6
gap> is_friendly( 220 );
284
gap> is_friendly( 284 );
220
gap> is_friendly( 200 );
0
  1. Ache todos os pares amigáveis de números entre 1 e 1000000.

Use a função sum_divisors escrita para Tarefa 1. Pode usar também a função Filtered sobre [1..1000000] (Seção 3.1).

8.5 Tarefa 4

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 (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.
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.
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.

Além de utulizar a função sum_divisors, vai precisar de listas (Seção 3.1), variáveis locais (Seção 5.6), e laços (Seção 5.2 e Seção 5.3). Pode precisar também a expressão break (Seção 5.8).

Este projeto foi inspirado pelo seguinte vídeo.