Ачат -- Форум математиков

Есть число, 19 например. Нужно его разложить на 4 взаимнопростых числа, сумма которых равна 19(3,4,5,7). Как реализовать?
Или пошлите на хороший форум, где трутся математики. Заранее благодарен.

 

Математики трутся здесь ---> dxdy

 

если не выпендриваться - то методом перебора, написав программу.
А если это тебе задали в рамках какой-нибудь учебной программы, и требуется решить логически... тогда я не знаю. Смахивает на мат.логику. Может как-нибудь через графы попробовать.
При этом, собственно, для 19 или другого маленького числа - это то можно перебрать все варианты и в уме.
А вот если у тебя будет какое-нибудь 1286 - тогда нужен чёткий план

 

Обычным циклом с условиями, на любом ЯП.

 

Ну, числа будут иметь порядка 9-15 знаков, так шо это капэц...

Буду благодарен за приблизительный план.

 

Может и бред написал, но вспомнил школьные времена

x+y+a+z=19
X любое число > или = 16, например 8
8+y+a+z=19
y+a+z=11
Y любое число > или = 9, например 3
3+a+z=11
a+z=8
A любое число > или = 7, например 2
2+z=8
z=6

 

Да, но тут еще нужна проверка на взаимную простоту...

 

9-15 знаков... пидец.
Ну чё, тогда мозговой штурм.
Значит, сначала нужно получить все простые числа, меньшие заданного.
Это удовольствие высчитывается заранее, всего один раз. (а вообще, они все уже давным давно высчитаны, можно взять готовые)
Далее - все слагаемые - это либо простые числа, либо их произведения. Простых чисел - не так много, а вот их произаедений много.
Высчитать все возможные произведения всех возможных простых чисел(меньших заданного), чтобы эти произведения тоже были меньше заданного (при этом произведения могут иметь хоть 10 хоть 20 множителей, являющихся простыми числами).
А затем пробовать складывать последние три цифры этих "всех возможных произведений", чтобы проверить - сходится с результатом или нет. Если сходится - проверять более подробно.

В общем выглядит как вычислительный адъ

 

На самом деле достаточно взять любые два взаимнопростых числа (не равных единице) и тогда все четыре будут автоматически взаимнопростые.
Т.е. дано число 1000.
Берём любые два взаимнопростых, например, 33 и 34.
Берём любые два других, которые в сумме с двумя первыми дадут тысячу: 1000-(33+34)=933 , например, 2+931.
Числа 2, 33, 34, 931 являются взаимнопростыми автоматически

 

Ыыыы, а я нашел простое решение)))))
>>> s=789
>>> h=s/2
>>> h
394.5
>>> h1=384
>>> h2=385 #h1+h2=s
>>> n1=233
>>> n2=h1-n1
>>> n2
151
>>> n3=351
>>> n4=h2-n3
>>> o=0
>>> for n in [n1,n2,n3,n4]:
o+=n


>>> o
769
Теперь только проверку на взаимную простоту прикрутить.

Тож ниче, вот только 2 и 34... Но покручу.

 

Берешь число, дальше проверяешь каждое число от нуля до данного числа является ли оно простым, например за формулой Мерсенна и Ферма. Дальше уже за каким-нибудь алгоритмом ищешь возможные комбинации.
Наверняка есть уже готовая такая программа, если найдешь - выложи, интересно взглянуть.

 

В математике есть такая проблема Гольдбаха (в некоторых физмат школах она даже в школьный курс входит). Она развита для бинарного и тренарного случая. В данном случае ее предлагается расширить на 4 компоненты.

В данном случае достаточно применить дважды бинарную теорему Гольдбаха. А именно: искомое число должно быть четным, ибо нечетное число невозможно разложить на 4 простых. Тогда это число можно попытаться разложить на сумму двух четных чисел. После этого для каждого полученного числа можно применить бинарную теорему Гольдбаха. Пользуйтесь.

 

Тут же тема не о простых числах, а о взаимнопростых

 

Нужны взаимно простые или попарно взаимно простые? Взаимно простые - когда для каждого числа из набора нет общего делителя, кроме 1, попарно .. - когда для любой пары.
Есть разница.

 

Все четыре должны быть взаимно простыми между собой.

 

Действительно, сразу не заметил. Тогда этот метод не годится.

В таком случае задача чем-то походит на решение диофантовых уравнений.

 

Не вижу проблемы, 10^15 помещается в 64 бита.

 

вот все простые числа из 19:

[2 3 5 7 11 13 17]

покажите мне хоть один вариант, когда у вас есть четыре слагаемых из представленного массива, чтобы получилось 19

PS: 4 в вашем варианте (3,4,5,7) - не простое число

задача "имеет решение", только если возможны повторы:

2 3 11 3

но тогда нарушается другое условие - "взаимнопростых числа", т.к. всегда будут повторы (тут 3 и 3 -два взаимно простых числа). Вывод - решения у задачи нет. Кто вам такую задачу дал и зачем, и главное - что вы сделали этому человеку

Ниже скрипт для поиграться (сырой и необкатанный, но основные моменты видны):

Code:

#!/usr/bin/perl
$nn=56; # Ваше число, которое надо разложить на сумму простых чисел
$nnn=4; # Минимальное кол-во слагаемых
push(@pers,2);
for(my $i=3;$i<$nn; $i+=2){
  my $flag=1;
  for(my $j=3; $j**2<=$i; $j+=2){if($i % $j==0){$flag=0;last;}}
  push(@pers,$i) if $flag;
}
print "\nAll simple numbers in $nn: [@pers] \n";
$size = @pers;
crack($size);
sub crack{
 $| = 1;
 $CharSet = shift;
 @RawString = ();
 for (my $i =0;$i<$CharSet;$i++){ $RawString[i] = 0;}
 do{
  for (my $i =0;$i<$CharSet;$i++){
   if ($RawString[$i] > $size){
    if ($i==$CharSet-1){
    $cnt=0;
    return false;
   }
   $RawString[$i+1]++;
   $RawString[$i]=0;
   }
  }
   $ret = "";
   $ret1 = 0;
   for (my $i=0;$i<$CharSet;$i++){ 
         $my=length($pers[$i]);  
         $ret = $ret."+".substr($pers[$i],$RawString[$i],$my);
         @pers1 = split /\+/,$ret;@pers1 = grep {$_} @pers1;@pers1=grep{$_!=1} @pers1;
         $size1=@pers1;
         print "Variants: $cnt\r";
         $ret1 = $ret1+substr($pers[$i],$RawString[$i],$my);
         #print "@pers1\n";
         if($ret1==$nn && $size1==$nnn){
           print "\n\n===> @pers1\n";
           exit; 
         }  
   }
   $cnt++;
   $RawString[0]++;
 }while($RawString[$CharSet-1]<$size);
}

 

Pashkela, в задаче речь не о простых числах, а о взаимно простых!

 

Для тек, кто будет интересоваться этой темой, оставлю здесь линк на аналогичную тему на dxdy. Там найден ответ.
http://dxdy.ru/post605334.html#p605334