БлогNot. Натуральные числа как предки и потомки

Натуральные числа как предки и потомки

Побалуемся ещё немного с факторизацией натуральных чисел из предыдущей заметки.

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

Например, число 46, имеющее третий уровень поколения, факторизуется в виде 2*23, а 2+23=25, следовательно, 25 (число второго уровня) является предком 46.

Прямым предком числа 25 будет число первого уровня 10, потому что 25=5*5, а 5+5=10.

В свою очередь, 10 имеет предком нулевого уровня простое число 7, поскольку 10 = 2*5, а 2+5=7. Потомком семёрки будет и число 12, ведь 12=2*2*3, а 2+2+3=7, следовательно, 7 - это предок 12.

В списке предков числа 46 мы должны увидеть 7, 10, 25.

У самих "порождающих" простых чисел будет уровень 0 и отсутствие предков, они сами "Великие Предки". Великими Предками всех чисел являются числа нулевого уровня от 1 до 5 включительно и далее все простые, но числа от 1 до 4 не имеют потомков, и лишь пятёрка является первым порождающим числом, причём, породит она только шестёрку (2*3=6, 2+3=5). Шестёрка - первое воспроизводящее число, у него 2 потомка, 8 и 9 (2*2*2=8 и 2+2+2=6, 3*3=9 и 3+3=6).

Итак, количество предков числа соответствует его "уровню" в списке поколений, а количество потомков, конечно, будет лавинообразно расти с увеличением исходного числа, у того же 46 будет уже 557 потомков. Плюс может сказаться ограниченность возможностей используемых нами стандартных контейнеров STL, поэтому ограничимся первой сотней чисел.

Так как количество шагов основного цикла здесь невелико, саму простоту числа можно определить и "по-школьному" (функция is_prime), а не решетом Эратосфена. Вот вам целая Библия чисел. Ниже прилагается исходник (консоль актуальной сборки Visual Studio 2019) и файл с генеалогией чисел от 1 до 100 включительно.

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
typedef unsigned long long integer;

// Получить всех предков n, n - не свой собственный предок
vector <integer> get_parents (const vector<integer>& parent, integer n) {
 vector <integer> result;
 for (integer a = parent[n]; a != 0 && a != n; ) {
  n = a;
  a = parent[n];
  result.push_back(n);
 }
 return result;
}

bool is_prime(integer n) {
 if (n < 2) return false;
 if (n % 2 == 0) return n == 2;
 for (integer p = 3; p * p <= n; p += 2) {
  if (n % p == 0) return false;
 }
 return true;
}

void print_vector (const vector<integer>& vec, ofstream &f) {
 if (vec.empty()) {
  f << "none" << endl; return;
 }
 auto i = vec.begin();
 f << *i++;
 for (; i != vec.end(); ++i) f << ", " << *i;
 f << endl;
}

int main () {
 //предел счёта в главном цикле, при увеличении сильно увеличивается время работы
 const size_t limit = 101;
 //контейнеры для предков и потомков
 vector <integer> parent (limit, 0);
 vector <vector <integer>> children (limit);
 //расчёты
 cout << "Calc: ";
 for (size_t prime = 0; prime < limit; prime++) {
  if (prime % 10 == 0) cout << prime << ' ';
  if (!is_prime(prime)) continue;
  children[prime].push_back(prime);
  for (size_t i = 0; i + prime < limit; i++) {
   integer s = i + prime;
   for (integer n : children[i]) {
    integer prod = n * prime;
    children[s].push_back(prod);
    if (prod < limit) parent[prod] = s;
   }
  }
 }
 //вывод результатов
 integer total_children = 0;
 ofstream f("parents_and_children.txt");
 if (!f) {
  cout << "Can't create parents_and_children.txt, check permissions, please" << endl;
  return 1;
 }
 cout << endl << "File: ";
 for (integer i = 1; i < limit; i++) {
  vector <integer> parents(get_parents(parent, i));
  f << "[" << i << "], level = " << parents.size() << endl;
  f << "Parents: ";
  sort(parents.begin(), parents.end());
  print_vector(parents, f);
  f << "Children: ";
  vector<integer>& desc = children[i];
  if (!desc.empty()) {
   sort (desc.begin(), desc.end());
   if (desc[0] == i) desc.erase(desc.begin());
   if (!desc.empty()) f << "total " << desc.size() << endl;
   else f << "none" << endl;
  }
  else f << "none" << endl;
  total_children += desc.size();
  if (!desc.empty()) print_vector(desc, f);
  f << endl;
  if (i % 10 == 0) cout << i << ' ';
 }
 f << "Total children: " << total_children;
 f.close();
 return 0;
}

 Скачать файл parents_and_children.txt в архиве .zip с Яндекс-диска (размер архива 2,7 Мб)

  • У числа 42 второй уровень (предки 7 и 12) и 372 потомка.
  • У числа 100, имеющего четвёртый уровень (предки: 5, 6, 9, 14) оказалось 40899 потомков.
  • Наименьшее натуральное число первого уровня это 6, второго - 8, третьего - 14, четвёртого - 26, пятого - 62, шестого - 134 (2*67=134 (69), 3*23=69 (26), 2*13=26 (15), 3*5=15 (8), 2*2*2=8 (6), 2*3=6 (5)). Похоже, что для наименьшего числа уровня L, L = 1,2,..., будут получаться соотношения L1=6, D2 = 2, LK = LK-1 + DK, DK+1=(MOD(K,2)==0 ? DK*3 : DK*2); K = 2, 3, ..., проверим этот факт:
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
     const int n = 10;
     vector <int> l(n+1),d(n+2);
     l[1] = 6; d[2] = 2;
     for (int k = 2; k < n; k++) {
      l[k] = l[k-1] + d[k];
      d[k+1] = k%2==0 ? d[k]*3 : d[k]*2;
      cout << k << ' ' << l[k] << ' ' << d[k] << endl;
     }
     return 0;
    }
    2 8 2
    3 14 6
    4 26 12
    5 62 36
    6 134 72
    7 350 216
    8 782 432
    9 2078 1296
  • Числа 7, 8, 9, 10 имеют 2, 3, 4 и 5 потомков соответственно.
  • Для первых 200 чисел программа сгенерирует файл размером 3605 Мб, у числа 200 определится 4 уровень и 9845164 потомка, но, похоже, мощности обычных контейнеров STL хватит для размещения всех потомков только до значения 129 включительно.
  • Уже у числа 14 три поколения предков (то есть, третий уровень) и 10 чисел-потомков, в том числе значение 100.
  • Тысяча - один из 30 потомков числа 21, тьма (10000) - один из 77 потомков числа 28, 100000 - один из 175 потомков числа 35, миллион - один из 372 потомков всё того же 42, 10 миллионов - один из 744 потомков значения 49, а у 100 миллионов родителем является число 56, у которого 1420 "детей". Миллиард порождён числом 63 как один из 2605 "братьев и сестёр", а триллион (10 в 12 степени по короткой шкале) - числом 84 как один из 13435 потомков. У квадриллиона с 15 нулями "папой" будет 105 (56826 потомков), у квинтиллиона с 18 нулями - 126 (208585 потомков). Как видим, десять в степени n, n = 1,2,... имеет предка, легко определяемого по формуле 7*n.
  • Количество потомков у каждого следующего числа не меньше, чем у предыдущего.
  • Среди проверенных чисел ни у кого не нашлось 6 или 9 потомков (а также 11, 13, 15, 17, 18, дальше "дырок" в цепочке значений количества потомков, естественно, будет подавляющее большинство).
  • Поскольку вычитания всё равно не существует (сбалансируйте систему счисления и будете иметь "все положительные числа"), а деление тут же выводит нас из множества натуральных чисел и нумерологии, Дерево Чисел, конечно, должно строиться только на умножении и сложении, как и сделано.

Ещё интересные классы чисел, связанные с простотой:

16.10.2021, 12:55 [360 просмотров]


теги: c++ алгоритм список математика числа памятка