Я это в конце концов понял, но вначале я рассуждал как Deosis, и мне тоже казалось, что это должно сильно ускорить поиск: для числа n количество его делителей d(n) растет очень медленно, см. ссылку: d(n)=O(n^ε) для любого ε.
Однако, в той же ссылке приведено, что сумма d(n) по всем n<N будет порядка N*lnN.
А при поиске вперед для любого n мы просматриваем N/n вариантов. Если просуммировать, то получим Sum(N/n)=N*Sum(1/n) ~ N*lnN, то есть, в среднем оба метода дают одинаковое количество итераций.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ShaleNumbers
{
public class ShaleSequence
{
private static readonly object syncRoot = new object();
private int Length;
private int[] Sequence;
private byte[] Bucket;
public ShaleSequence(int N, int a, int b)
{
Sequence = new int[N];
Bucket = new byte[N];
for (int i = 0; i < Bucket.Length; i++) Bucket[i] = 1;
Add(a);
Add(b);
}
public int N => Bucket.Length;
public int[] ToArray() => Sequence.Take(Length).ToArray();
public override string ToString() => String.Join(" ", ToArray());
public bool IsFound => Length == Sequence.Length;
private bool IsSet(int n) => Bucket[n - 1] == 1;
private void Add(int x)
{
Sequence[Length++] = x;
Bucket[x - 1] = 0;
}
private void Remove(int x)
{
Length--;
Bucket[x - 1] = 1;
}
public void Scan()
{
Scan(Sequence[0], Sequence[1]);
}
private void Scan(int a, int b)
{
if (IsFound)
{
string info = ToString();
lock (syncRoot) Console.WriteLine(info);
return;
}
for (int c = a - (b % a); c <= N; c += a)
{
if (!IsSet(c)) continue;
Add(c);
Scan(b, c);
Remove(c);
}
}
public static void FindShaleSequences(int N)
{
DateTime start = DateTime.UtcNow;
List<Task> tasks = new List<Task>();
for (int a = 1; a <= N; a++)
{
for (int b = 1; b <= N; b++)
{
if (a == b) continue;
ShaleSequence sequence = new ShaleSequence(N, a, b);
Task task = Task.Factory.StartNew(sequence.Scan);
tasks.Add(task);
}
}
Task.WaitAll(tasks.ToArray());
DateTime end = DateTime.UtcNow;
Console.WriteLine($"N: {N}; Time: {(int)(end - start).TotalSeconds} sec");
}
}
public class Program
{
public static void Main(string[] args)
{
for(int N = 3; N <= 100; N++)
{
ShaleSequence.FindShaleSequences(N);
}
}
}
}
Да, я тоже дошел до N^N/N! = O(e^N) ( кстати, получилась хорошая задачка! ), но дальше не смог продвинуться: для улучшения оценки надо учитывать, что, так как все числа должны быть разные, много вариантов для третего числа отбрасываются.
Я, кстати, посчитал количество обработанных последовательностей для каждого N. Что и можно было ожидать, их количество растет ровно с той же скоростью, что и сложность алгоритма:
Да, это одна из первых оптимизаций, которые я пробовал. Удивительно, но это не принесло никакого эффекта, время работы практически не изменилось!
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Действительно, похоже на e/2! Я, правда, не представляю, как это можно доказать (хотя достаточно просто показать, что скорость роста не превосходит e^N). Но например, если доказать, что для большинства последовательностей в переборе алгоритм доходит как минимум до длины N/2, то это даст нижнюю оценку в (e/2)^N.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Однако, в той же ссылке приведено, что сумма d(n) по всем n<N будет порядка N*lnN.
А при поиске вперед для любого n мы просматриваем N/n вариантов. Если просуммировать, то получим Sum(N/n)=N*Sum(1/n) ~ N*lnN, то есть, в среднем оба метода дают одинаковое количество итераций.
Я, кстати, посчитал количество обработанных последовательностей для каждого N. Что и можно было ожидать, их количество растет ровно с той же скоростью, что и сложность алгоритма:
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Такой вопрос: сколько времени у вас работала программа для N=51?