Антимагические квадраты

[Nataly-Mak]

Проверяю следующую структуру:

0 2 8 14 
22 24 30 36 
48 50 56 62 
70 72 78 84

Ранжирую массив:

0  2  8  14  22  24  30  36  48  50  56  62  70  72  78  84

(ранжированный массив удобнее проверять)
Здесь получается тоже невозможно, ибо 0, 2 и 22 дают все три вычета по модулю 3.
Я правильно поняла?

Эх-ма...
Тогда, пожалуй, найти подходящую структуру не так просто. Мало найти квадрат Стенли из возможных разностей, надо ещё, чтобы эти разности могли в принципе дать нужные простые числа.

Следующие структуры

0  2  14  52 
22  24  36  74 
28  30  42  80 
32  34  46  84

0  2  26  50 
22  24  48  72 
30  32  56  80 
34  36  60  84

тоже невозможны.

Все приглашаются к поиску возможной структуры (квадрат Стенли из чётных чисел 0 - 84), чтобы эта структура могла дать набор из 16 последовательных простых чисел.
Хотя бы могла дать, уже не говорю о том, чтобы обязательно дала.

-- Ср мар 26, 2014 15:54:04 --

А вот такая структура возможна

0  4  12  54 
6  10  18  60 
24  28  36  78 
30  34  42  84 

По модулю 3 есть только остатки 0 и 1.

А по следующим модулям тоже надо проверять? И до какого модуля?

По модулю 4 остатки только 0 и 2.
А вот по модулю 5 полный набор остатков - 0, 1, 2, 3,4
например: 0, 4, 12, 6, 18

Опять не годится?
Ужас!

-- Ср мар 26, 2014 16:24:42 --

Ещё одну структуру проверила для модулей от 3 до 7:

0  4  40  54 
6  10  46  60 
12  16  52  66 
30  34  70  84

Полного класса вычетов для этих модулей нет.
Дальше надо проверять (для следующих модулей)?

[Nataly-Mak]

Ну вот, на самом интересном месте все замолчали

Я проверила эту конструкцию

0  4  40  54 
6  10  46  60 
12  16  52  66 
30  34  70  84

для всех модулей от 3 до 16 включительно.
У меня получилось, что невозможных комбинаций разностей (для существования простых чисел) данная конструкция не содержит.

Это правильно

-- Чт мар 27, 2014 07:05:03 --

Если эта конструкция действительно годная, тогда на огромном пространстве массива простых чисел из интервала (2, 4164532312868707261) требуется найти такой набор из 16 последовательных простых чисел:

0  4  6  10  12  16  30  34  40  46  52  54  60  66  70  84

И если это решение будет найдено, оно будет лучше решения Andersen, но ещё не факт, что оно будет наименьшим.

-- Чт мар 27, 2014 07:14:21 --

Интересно, что первые 6 членов последовательности сразу находятся:

0  4  6  10  12  16 ...

7, 11, 13, 17, 19, 23, ...

Следующий член тоже простое число (37), но уже не последовательное.

-- Чт мар 27, 2014 07:26:22 --

Однако...
последние два члена - 77 и 91 - не простые числа.
Это почему они возникли?
Значит, структура моя опять негодная?

-- Чт мар 27, 2014 07:36:57 --

Почему 77 и 91 делятся на 7, понятно.
0, 70, 84 - все эти разности дают 0 по модулю 7.

-- Чт мар 27, 2014 07:46:32 --

Это конструкция Andersen:

0  6  10  16  18  28  30  40  42  48  52  58  60  70  72  82

При стартовом числе 7 тоже получаем не простые числа:

7, 13, 17, 23, 25, 35, ...

Делаю вывод: годная конструкция не гарантирует, что при любом стартовом простом числе в ней не появятся не простые числа.

[Nataly-Mak]

Поиграла в WolframAlpha

Задаю код:

Select[Range[0,84],PrimeQ[7+#]&]

нахожу последовательность простых чисел.
Затем меняю стартовое число и снова нахожу последовательность.
Получились последовательности весьма похожие на мою конструкцию:

St=7
{0, 4, 6, 10, 12, 16, 22, 24, 30, 34, 36, 40, 46, 52, 54, 60, 64, 66, 72, 76, 82}
St=13
{0, 4, 6, 10, 16, 18, 24, 28, 30, 34, 40, 46, 48, 54, 58, 60, 66, 70, 76, 84}
St=31
{0, 6, 10, 12, 16, 22, 28, 30, 36, 40, 42, 48, 52, 58, 66, 70, 72, 76, 78, 82}
St=37
{0, 4, 6, 10, 16, 22, 24, 30, 34, 36, 42, 46, 52, 60, 64, 66, 70, 72, 76}
St=67
{0, 4, 6, 12, 16, 22, 30, 34, 36, 40, 42, 46, 60, 64, 70, 72, 82, 84}
St=73
{0, 6, 10, 16, 24, 28, 30, 34, 36, 40, 54, 58, 64, 66, 76, 78, 84}
St=97
{0, 4, 6, 10, 12, 16, 30, 34, 40, 42, 52, 54, 60, 66, 70, 76, 82, 84}

Последняя вообще очень сильно похожа, сравните --- моя конструкция:

0 4 6 10 12 16 30 34 40 46 52 54 60 66 70 84

Отсутствует в последовательности, сгенерированной WolframAlpha, только разность 46. Ну и ещё есть два простых числа (соответствующие разностям 76 и 82), которые в моей конструкции будут пропущены.

И решение почти найдено точнее - приближение к решению.
Вот оно:

97 101 137 151 
103 107 143 157 
109 113 149 163 
127 131 167 181

Одно число в этом решении не простое (143) и число 181 не является последовательным (так как два простых числа пропущены - 173 и 179.

Теперь вопрос:
можно в Mathematica написать программку, чтобы эта процедура (которую я выполняю вручную) выполнялась автоматически?

[Jarek]

Do[Print[St," ",Select[Range[0,84],PrimeQ[St+#]&]],{St,7,100,6}]

Do[Print[St," ",Length[p=Select[Range[0,84],PrimeQ[St+#]&]]," ",p],{St,7,100,6}]

[Nataly-Mak]

О!
Jarek
спасибо огромное, но... я не знаю язык Mathematica

Не могли бы вы пояснить, что будут делать приведённые вами коды?

Сравнить сгенерированные последовательности с моей конструкцией программка сможет?

[Jarek]

The second code will write down:
the first prime,
the length of the list,
the list of differences.
It will be done for the starting prime from 7 to 100 with increments of 6.

Mathematica can compare the lists with yours, but you cannot really count on finding the exact match in a finite time that way. Mathematica is a powerfull tool, but is very slow, so it is not suitable for extensive searches which require a lot of computer time.

The following sample code

Do[p=Select[Range[0,8],PrimeQ[St+#]&];If[p==={0,2,6,8},Print[St]],{St,5,200,6}]

will find starting primes of prime quadruplets.

[Nataly-Mak]

Спасибо, немножко поняла
Чтобы всё понять, мне придётся изучить язык Mathematica.

Вы считаете, что программа в Mathematica не справится с этой задачей за реальное время?

Тогда надо написать программу на другом языке программирования, который работает быстрее.

[Nataly-Mak]

Написала простенькую программку на QBASIC.
Проверяется очень быстро.
У меня есть массив из 3 000 000 простых чисел, проверился мгновенно, не успела глазом моргнуть

Точно моя конструкция не нашлась, но нашлись точно такие же первые 10 разностей:

0  4  6  10  12  16  30  34  40  46

при стартовом простом чисел 16057.
Это уже хорошее совпадение, более половины последовательности.

Дописала последовательность по разностям моей конструкции, получилось:

16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16109, 16111, 16117, 16123, 16127, 16141

Влезли три не простых числа (они выделены цветом); ну и, кроме того, последнее число не последовательное, так как пропущено простое число 16139.
Но всё же есть ещё одно приближение к решению.

Эх! Мне бы большой массив простых, я бы его сейчас мигом проверила

[Someone]

Nataly-Mak в сообщении #841693 писал(а):

Эх! Мне бы большой массив простых, я бы его сейчас мигом проверила

http://yadi.sk/d/KH0n-ne_LKcoz

[Nataly-Mak]

Someone
Спасибо.
Массив скачала. В распакованном виде у меня файл 101830 Кб.
Да-а-а-а, солидный массив. Интересно, сколько он содержит простых чисел? Или ещё такой вопрос: в каком интервале натуральных чисел находятся простые числа этого массива? От самого начала до...?

Попробовала проверку.
Похоже, от такого массива мой QBASIC моментально одурел
Попробовала сразу же после загрузки файла в программу вывести в другой файл несколько чисел, вот что получила:

-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 
-2147483648 

При этом мой массив, содержащий 3000000 простых чисел, проверяется нормально.
Ну, это же маленький массив.

Остаётся выложить мою примитивную программку проверки на QBASIC; может быть, кто-нибудь попробует переписать её на другом языке и проверить этот огромный массив простых, выложенный Someone.

(Оффтоп)

#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
 LOCAL K,I,N AS LONG

N=3000000
DIM P(N) AS LONG, A(16) AS LONG, C(20) AS LONG
OPEN "primenew.TXT" FOR INPUT AS #1
FOR I=1 TO N
INPUT #1,P(I)
NEXT I
CLOSE #1

OPEN "A23.TXT" FOR INPUT AS #1
FOR I=1 TO 16
INPUT #1,A(I)
NEXT I
CLOSE #1

K=1
2 C(1)=P(K)
C(2)=P(K+1)-P(K)
IF C(2)=A(2) THEN 10
GOTO 100

10 C(3)=P(K+2)-P(K)
IF C(3)=A(3) THEN 12
GOTO 100

12 C(4)=P(K+3)-P(K)
IF C(4)=A(4) THEN 14
GOTO 100

14 C(5)=P(K+4)-P(K)
IF C(5)=A(5) THEN 16
GOTO 100

16 C(6)=P(K+5)-P(K)
IF C(6)=A(6) THEN 18
GOTO 100

18 C(7)=P(K+6)-P(K)
IF C(7)=A(7) THEN 20
GOTO 100

20 C(8)=P(K+7)-P(K)
IF C(8)=A(8) THEN 22
GOTO 100

22 C(9)=P(K+8)-P(K)
IF C(9)=A(9) THEN 24
GOTO 100

24 C(10)=P(K+9)-P(K)
IF C(10)=A(10) THEN 26
GOTO 100

26 C(11)=P(K+10)-P(K)
IF C(11)=A(11) THEN 28
GOTO 100

28 C(12)=P(K+11)-P(K)
IF C(12)=A(12) THEN 30
GOTO 100

30 C(13)=P(K+12)-P(K)
IF C(13)=A(13) THEN 32
GOTO 100

32 C(14)=P(K+13)-P(K)
IF C(14)=A(14) THEN 34
GOTO 100

34 C(15)=P(K+14)-P(K)
IF C(15)=A(15) THEN 36
GOTO 100

36 C(16)=P(K+15)-P(K)
IF C(16)=A(16) THEN 300

100 K=K+1
IF K>N-16 THEN 1000
GOTO 2

300 OPEN "A15.TXT" FOR OUTPUT AS #1
FOR I=1 TO 16:PRINT #1,C(I);:NEXT I
CLOSE #1
GOTO 1002

1000 OPEN "A17.TXT" FOR OUTPUT AS #1
PRINT #1,C(1)
CLOSE #1
1002 END

END FUNCTION

Вряд ли требуются пояснения к этой простенькой программке.
[Я даже не организовала цикл для проверки, всё расписала для каждого члена ]

В файле A23.txt находится моя конструкция, которая проверяется:

0 4 6 10 12 16 30 34 40 46 52 54 60 66 70 84

P.S. Если кто-то вдруг будет проверять...
Интересны совпадения, начиная с 11-го члена последовательности, так как последовательность, совпадающую с моей конструкцией 10 членами, я уже нашла.
Вероятность полного совпадения очень мала.

[Someone]

Nataly-Mak в сообщении #842097 писал(а):

Или ещё такой вопрос: в каком интервале натуральных чисел находятся простые числа этого массива?

До $200\,000\,000$.

Nataly-Mak в сообщении #842097 писал(а):

сколько он содержит простых чисел?

Программа sieve.exe утверждает, что $11\,078\,937$. На моём компьютере она их все находит за 8 секунд.
Программа написана на языке C, и предназначена для печати простых чисел на экране. Заставить её вывести результаты в файл можно, но надо использовать средства DOS для перенаправления ввода и вывода. После удаления из файла ненужных сообщений и исправления первого простого числа с 1 на 2 получается то, что получилось: список последовательных простых чисел, разделённых знаками табуляции (код $09H$).

Блокнот этот файл открыть не может (видимо, из-за большого размера).

Nataly-Mak в сообщении #842097 писал(а):

Похоже, от такого массива мой QBASIC моментально одурел

Я не в курсе, какие в QBASIC есть средства ввода. Формат файла я Вам сообщил, думайте сами. Может быть, вводить в двоичном формате и "вручную" преобразовывать текст в числа. Цифра $n$ имеет шестнадцатеричный код $3nH$ (десятичное число $48+n$). Признаком конца числа служит упомянутый выше код табуляции.

Используется синтаксис C

#include <stdio.h>
#include <malloc.h>
#include <time.h>

#define TEST(f,x)       (*(f+(x)/16)&(1<<(((x)%16L)/2)))
#define SET(f,x)        *(f+(x)/16)|=1<<(((x)%16L)/2)

int
main(int argc, char *argv[])
{
  unsigned char *feld=NULL, *zzz;
  unsigned long teste=1, max, mom, hits=1, count, alloc, s=0, e=1;
  time_t begin;

  if (argc > 1)
    max = atol (argv[1]) + 10000;
  else
    max = 14010000L;

  while (feld==NULL)
        zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

  for (count=0; count<alloc; count++) *zzz++ = 0x00;

  printf ("Searching prime numbers to : %ld\n", max);

  begin = time (NULL);
  while ((teste+=2) < max)
        if (!TEST(feld, teste)) {
                if  (++hits%2000L==0) {printf (" %ld. prime number\x0d", hits); fflush(stdout);}
                for (mom=3L*teste; mom<max; mom+=teste<<1) SET (feld, mom);
                }

  printf (" %ld prime numbers foundn %ld secs.\n\nShow prime numbers", 
          hits, time(NULL)-begin);

  while (s<e) {
        printf ("\n\nStart of Area : "); fflush (stdout); scanf ("%ld", &s);
        printf ("End   of Area : ");     fflush (stdout); scanf ("%ld", &e);

        count=s-2; if (s%2==0) count++;
        while ((count+=2)<e) if (!TEST(feld,count)) printf ("%ld\t", count);
        }
  free (feld);
  return 0;
}

-- Пт мар 28, 2014 12:48:47 --

P.S. Программа не моя, но она находится в свободном доступе.

[Nataly-Mak]

Цитата:

Блокнот этот файл открыть не может (видимо, из-за большого размера.

Это я даже и не пыталась сделать.
Скачав выложенный вами архив, я извлекла из него файл в папку.
Увидела размер этого файла, формат его вроде бы txt.
Открывать, конечно, не стала, ибо имею опыт открытия больших текстовых файлов уже довольно большой.

Сразу попыталась проверить по своей программе первые 3000000 чисел.
Однако сразу поняла, что что-то идёт не так. Вывела тогда несколько чисел в другой файл и увидела то, что здесь показано.
То есть никаких простых чисел моя программа "не видит" в файле, полученном из скачанного архива.

Цитата:

Формат файла я Вам сообщил...

Лучше поздно...
Спасибо.

-- Пт мар 28, 2014 13:23:44 --

Действую кустарным методом.
У меня есть отличная программа генерации простых чисел (автор программы svb).
Так как первая порция простых чисел (в количестве 3 000 000) проверена, генерирую следующую порцию - в интервале (49 970 000, 70 000 000). В этом интервале оказалось всего 1 118 630 простых чисел. Этот массив моя программка проверяет шутя.
Вот что найдено:

53204857  4  6  10  12  16  30  0  0  0  0  0  0  0  0  0

то есть совпадение есть только первых 7 членов последовательности.

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

-- Пт мар 28, 2014 13:46:16 --

В следующей порции найдено:

72610117  4  6  10  12  16  30  34  40  0  0  0  0  0  0  0

Уже проверены все простые в интервале (2, 100 000 000).

[Nataly-Mak]

Someone в сообщении #842192 писал(а):

Программа sieve.exe утверждает, что $11\,078\,937$. На моём компьютере она их все находит за 8 секунд.

Правильно утверждает.
Сгенерировала порциями все простые числа в интервале [2, 200 000 000].

[2, 30 000 000] - 1857859 простых чисел
[30 000 001, 60 000 000] - 1704256
[60 000 001, 90 000 000] - 1654839
[90 000 001, 120 000 000] - 1624694
[120 000 001, 150 000 000] - 1602748
[150 000 001, 180 000 000] - 1585989
[180 000 001, 200 000 000] - 1048552

Итого в интервале [2, 200 000 000] 11078937 простых чисел.

Кстати, простые числа в указанном интервале программой svb генерируются за несколько секунд. Проверяется одна такая порция по моей программе 3-5 секунд.
И никакой мороки с форматом, ибо числа записываются в файл в нормальном формате, который понимает программа на QBASIC, и думаю, поймёт любая другая программа. Это обычный формат текстового файла.

[whitefox]

Альфа говорит тоже самое:

[Nataly-Mak]

У-р-а-а-а-а! Все единодушны

whitefox
спасибо, что показали, как это определять в WolframAlpha. Теперь и это знаю

-- Сб мар 29, 2014 09:29:40 --

А вот тут WolframAlpha немножко растерялся и... смог предложить ответ только в виде интеграла



Задано

PrimePi[4164532312868707261]