Nome: Alexandre Gomes Pinto
RA: 090240
Monografia
Inteiros Consecutivos Com a Mesma Quantidade de
Divisores Principais
Resumo
Um divisor principal de um número inteiro positivo n é qualquer potência de um
primo que divide n, digamos pa | n, em que a é máximo (a é um inteiro positivo, pa+1
não divide n). Dizemos então que pa é um divisor principal de n, ou pa || n.
Para cada inteiro n ≥ 0, chamamos de Pn o conjunto de todos inteiros positivos
com exatamente n divisores principais. Alguns exemplos são:
P0 = {1},
P1 = {2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, ... }
P2 = {6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 33, 34, 35, ... }
P3 = {30, 42, 60, 66, 70, 78, 84, 90, ... }
Estamos interessados em saber qual é a maior seqüência de inteiros
consecutivos em um conjunto Pn. Sabemos que tal seqüência existe, pois:
Seja M o produto dos primeiros n + 1 primos. Então M ∈ Pn+1. Logo, qualquer
seqüência de M inteiros consecutivos contém um múltiplo de M, portanto qualquer
seqüência de Pn tem um tamanho menor que M.
Abaixo segue um programa em linguagem C que retorna os elementos de um
Pn, limitados a um valor máximo de 7500. O programa é capaz de calcular o conjunto
Pn para n = 1, 2, 3. Os resultados encontrados por ele coincidem com os do artigo no
qual este trabalho se baseou, “Consecutive Integers with Equally Many Principal
Divisors – Roger B. Eggleton and James A. Macdougall”.
Exemplo de funcionamento:
Digite o numero de divisores principais (1, 2 ou 3) dos elementos do conjunto:
Entrada: 2
Digite o valor máximo do conjunto (número entre 2 e 7500):
Entrada: 100
Saída: (Números do conjunto)
Maximal run: 6
Starting with: 91
Caso existam mais seqüências com o mesmo tamanho, o programa exibirá
mais inteiros iniciais, cobrindo assim todas as maiores seqüências no intervalo
especificado. O valor máximo do conjunto não pôde ser maior devido a grande
quantidade de cálculos para P3.
#include <stdio.h>
#include <math.h>
void Um(int v[],int p[], int b);
void Dois(int v[],int p[], int b);
void Tres(int v[],int p[], int b);
void Primos(int p[], int b);
void Imprime(int b, int run, int matriz[][20], int v[]);
void Maximos(int b, int *run, int matriz[][20], int v[]);
int main() {
int v[7501], p[7501], i, j, a, b, c, n, m, e, f, run;
int matriz[10][20];
printf ("Digite o numero de divisores principais (1, 2 ou 3) dos elementos do conjunto: \n");
scanf ("%d",&n);
printf ("Digite o valor maximo do conjunto (numero entre 2 e 7500): \n");
scanf ("%d",&b);
// Inicializa o vetor p(primos), o vetor v(divisores principais) e a matriz que guardara as maiores sequencias do
conjunto
for (i = 0; i <= 7500; i++) {
p[i] = i;
}
for (i = 0; i <= 7500; i++) {
v[i] = 0;
}
for (i = 0; i <10; i++) {
for (j = 0; j < 20; j++) {
matriz[i][j] = 0;
}
}
Primos(p,b);
if (n == 1)
Um(v,p,b);
else if (n == 2)
Dois(v,p,b);
else if (n == 3)
Tres(v,p,b);
Maximos(b,&run,matriz,v);
Imprime(b,run,matriz,v);
return 0;
}
//Computa o vetor dos numeros primos
void Primos(int p[], int b){
int i,a;
for (i = 2; i*i <= b;) {
for (a = 2; (i*a <= b); a++) {
p[i*a] = 0;
}
for (i++; p[i] == 0;) {
i++;
}
}
}
//Computa P1
void Um(int v[],int p[], int b) {
int e, c, i;
for (i = 2; i < 7501; i++) {
if (p[i] !=0) {
for (e = 1; pow(p[i],e) <= b; e++) {
c = pow(p[i],e);
v[c] = c;
}
}
}
}
//Computa P2
void Dois(int v[],int p[], int b) {
int e, f, i, j, a, c;
for (i = 2; i < 7501; i++) {
if (p[i] !=0) {
for (e = 1; pow(p[i],e) <= b; e++) {
for (j = i+1; j < 7501; j++) {
if (p[j] != 0) {
for (f = 1; pow(p[j],f) <= b; f++) {
c = pow(p[i],e);
a = pow(p[j],f);
c = c*a;
if (c <= b) {
v[c] = c;
}
}
}
}
}
}
}
}
//Computa P3
void Tres(int v[],int p[], int b) {
int e, f, g, i, j, k, a, c;
for (i = 2; i < 7501; i++) {
if (p[i] !=0) {
for (e = 1; pow(p[i],e) <= b/6; e++) {
for (j = i+1; j < 7501; j++) {
if (p[j] != 0) {
for (f = 1; pow(p[j],f) <= b/6; f++) {
for (k = j+1; k < 7501; k++) {
if (p[k] != 0) {
for (g = 1; pow(p[k],g) <= b/6; g++) {
c = pow(p[i],e);
a = pow(p[j],f);
c = c*a;
a = pow(p[k],g);
c = c*a;
if (c <= b) {
v[c] = c;
}
}
}
}
}
}
}
}
}
}
}
//Encontra as maiores sequencias
void Maximos(int b, int *run, int matriz[][20], int v[]) {
int i, c, m, f;
for ( i = 0, c = 0, m = 1, *run = 1; i <= b; i++) {
if (v[i] != 0) {
c++;
if (c >= *run) {
*run = c;
m = v[i];
for (f = 0; f < 20; f++) {
if (matriz[*run][f] == 0) {
matriz[*run][f] = v[i];
f = 20;
}
}
}
}
if (v[i] == 0) {
c = 0;
}
}
}
//Imprime os vetores e as maiores sequencias encontradas
void Imprime(int b, int run, int matriz[][20], int v[]) {
int i,j;
printf("\n");
for (i = 2; i <= b; i++) {
if (v[i] != 0) {
printf("%5d",v[i]);
}
}
printf("\n\n");
printf(" Maximal run: %d\n
for (j = 0; j < 20; j++) {
Starting with: ", run);
if(matriz[run][j] !=0) {
printf("%d ", matriz[run][j]+1-run);
}
}
printf("\n");
}