Encontrar as parcelas que compõem uma soma
Enviado: 18 Jul 2020, 22:59
Prezados, boa noite. Esta é a minha primeira postagem aqui no Fórum. Perdoem-me se eu não utilizar uma linguagem matemática adequada, pois não sou desta área, embora trabalhe um pouco com ela. Tenho um problema computacional que gostaria de avaliar com vocês alguma solução eficiente.
Sejam p1, p2, p3, ..., pn o subconjunto de números primos contido no conjunto dos primeiros 64 números primos acima de 1000.
Problema: sabendo-se que todos, nenhum ou aleatoriamente alguns destes números primos compõem uma soma, a partir da soma informada, identificar quais são os números que a compõem. Obviamente, quando a soma é zero, nenhum número primo é utilizado e quando a soma corresponde a soma dos 64 números primos acima de 1000, todos eles compõem a soma. Todavia, a depender da situação somente alguns destes primos fazem parte da soma. Daí a necessidade de localizá-los rapidamente.
No problema são conhecidas as seguintes informações:
• O universo correspondente aos primeiros 64 números primos acima de 1000;
• O valor da soma dos 64 números primos deste universo;
• O valor da soma informada;
• O número n de parcelas que compõem a soma.
Se o problema tiver solução mais simples substituindo-se os 64 números primos por outra sequência, como uma PA, PG ou resultado de função (trigonométrica, logaritmo, etc.), peço a gentileza de discorrer. O conjunto dos primeiros 64 números primos acima de 1000 foi escolhido porque nenhum de seus componentes pode ser composto pela soma de outros componentes do mesmo conjunto.
Limitações: em razão de ser um problema computacional, fica inviável fazer a combinação aleatória ou sequenciada dos números e testa-las contra a soma. Assim, o método, se existir, deve ser mais eficiente. Ainda, multiplicar os número ou usar potências de 2 para depois fatorar também se mostra inviável em função da limitação para o cálculo e armazenamento do resultado da multiplicação.
Exemplo: sabendo que a soma de primos é 15493, quais números dentre os primeiros 64 primos acima de 1000 a compõe? O algoritmo, se existir, deve encontrar uma maneira eficiente de encontrar os primos 1039, 1051, 1061, 1091, 1103, 1117, 1123, 1249, 1259, 1283, 1297, 1367 e 1453.
Para facilidade, informa-se os primeiros 64 números primos acima de 1000:
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459.
Aceito qualquer sugestão!
Grato por seu tempo.
Sejam p1, p2, p3, ..., pn o subconjunto de números primos contido no conjunto dos primeiros 64 números primos acima de 1000.
Problema: sabendo-se que todos, nenhum ou aleatoriamente alguns destes números primos compõem uma soma, a partir da soma informada, identificar quais são os números que a compõem. Obviamente, quando a soma é zero, nenhum número primo é utilizado e quando a soma corresponde a soma dos 64 números primos acima de 1000, todos eles compõem a soma. Todavia, a depender da situação somente alguns destes primos fazem parte da soma. Daí a necessidade de localizá-los rapidamente.
No problema são conhecidas as seguintes informações:
• O universo correspondente aos primeiros 64 números primos acima de 1000;
• O valor da soma dos 64 números primos deste universo;
• O valor da soma informada;
• O número n de parcelas que compõem a soma.
Se o problema tiver solução mais simples substituindo-se os 64 números primos por outra sequência, como uma PA, PG ou resultado de função (trigonométrica, logaritmo, etc.), peço a gentileza de discorrer. O conjunto dos primeiros 64 números primos acima de 1000 foi escolhido porque nenhum de seus componentes pode ser composto pela soma de outros componentes do mesmo conjunto.
Limitações: em razão de ser um problema computacional, fica inviável fazer a combinação aleatória ou sequenciada dos números e testa-las contra a soma. Assim, o método, se existir, deve ser mais eficiente. Ainda, multiplicar os número ou usar potências de 2 para depois fatorar também se mostra inviável em função da limitação para o cálculo e armazenamento do resultado da multiplicação.
Exemplo: sabendo que a soma de primos é 15493, quais números dentre os primeiros 64 primos acima de 1000 a compõe? O algoritmo, se existir, deve encontrar uma maneira eficiente de encontrar os primos 1039, 1051, 1061, 1091, 1103, 1117, 1123, 1249, 1259, 1283, 1297, 1367 e 1453.
Para facilidade, informa-se os primeiros 64 números primos acima de 1000:
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459.
Aceito qualquer sugestão!
Grato por seu tempo.