Сколько существует прыгающих чисел, меньше 10^65?

[Ozzzzi]

Здравствуйте!
Подскажите пожалуйста, в чем может быть проблема. Не выводит конесный результат.

/*Если в числе все цифры не меньше стоящих слева от них, оно называется увеличивающимся. Пример - 133456.
 Соответственно, если числа не меньше стоящих справа, оно называется убывающим. Пример: 66420. 
 Числа, которые не являются ни возрастающими, ни убывающими мы будет называть прыгающим. 
 Сколько существует прыгающих чисел, меньше 10^65?*/
using System;
using System.Numerics;


namespace Задача_прыгающие_числа_
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger c;
            BigInteger max = BigInteger.Pow(10, 65);
            Console.WriteLine("Min = 1");
            Console.WriteLine("Max = " + max);
            BigInteger summ = 0;
            for (c = 0; c < max; c++)
            {
               if (IsJumpNum.IsJmpNm(c)) summ++;
               // Console.WriteLine("SUMM = " + summ);
            }
            var result = summ.ToString();
            Console.WriteLine("SUMM = " + result);
            Console.ReadLine();
        }
    }
}

class IsJumpNum
{
    static public bool IsJmpNm(BigInteger i)
    {
        int inc = 0; int dec = 0;
        var n = i.ToString().ToCharArray();
        //Console.WriteLine("Length = " + n.Length);
        for (int k = 0; k < n.Length - 1; k++)
        {
            if (n[k] >= n[k + 1]) inc++;
            if (n[k] <= n[k + 1]) dec++;
        }
        if (inc != 0 && dec != 0)
            return true;
        else
            return false;
    }
}

[veniside]

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

хинт 1: 10 в 65 — это реально офигенно невообразимо огромеднейшее число, и проще пронумеровать все атомы во вселенной зелёным маркером, чем дождаться, пока данный цикл закончится.

хинт 2: нужно идти другим путём

хинт 3: я бы посчитал, а сколько может быть убывающих и возрастающих чисел в этом диапазоне (только не в цикле, бога ради!). все остальные будут "прыгающими".

[Ozzzzi]

не знаете другого пути?)

[bondik]

Если решать в лоб то я попробовал бы на Cuda. GPU иногда дает фантастические результаты...

[veniside]

не знаете другого пути?)

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


подсчитать количество различных невозрастающих (или неубывающих) последовательностей, длиной от 1 до 65 и состоящих из цифр от 0 до 9 можно разными способами.

можно запустить 65 циклов, типа:

int sum = 0;

for (int i00 = 0; i00 <= 9; i00++)
  for (int i01 = i00; i01 <= 9; i01++)
    for (int i02 = i01; i02 <= 9; i02++)

//... и так далее до:

            for (int i64 = i63; i64 <= 9; i64++)
              sum++;

но, во-первых, это не красиво, а, во-вторых, работает долговато. Солнце не погаснет, конечно, но подождать часик или два прийдётся.

лично я решил через рекурсивную матрицу:

// код на js, если шо
// всего 650 ведёр, и золотой ключик у нас в кармане

const   digits = 10;
const   rounds = 65;

var a = new Array(digits);

for (var i = digits - 1; i >= 0; i--) {
    //
    a[i] = new Array(rounds);
    //
    for (var j = 0; j < rounds; j++)
    {
        if (digits - 1 == i)
            a[i][j] = 1;
        else    
        {
            if (0 == j)
                a[i][j] = a[i + 1][0] + 1;
            else
                a[i][j] = a[i + 1][j] + a[i][j - 1];
        }
    }
}    
    
console.log(a[0][rounds - 1]);

Не берусь на 100% утверждать, что я нигде не ошибся, но если принять это решение за верное, получаем количество "прыгающих" числел = 10^65 - 110524147514 * 2.

решать в лоб то я попробовал бы на Cuda

ну давайте попробуем. Допустим, у нас есть супер-мега жпу, который работает на частоте 1 петагерц (10^15 герц) в составе которого есть ну, допустим, 1 миллиард (10^9) процессоров. Предположим, мы написали чудо-программу, которая за 1 такт одного такого процессора обрабатывает 1 комбинацию. Итого, за 1 секунду наш программно-аппаратный чудо-комплекс будет способен обработать ни много, ни мало, а целых 10^24 комбинаций. Отлично! Так, минутку.. всего комбинаций у нас 10^65, т.е. потребуется всего-навсего 10^41 секунд, чтобы получить желанный результат. Для сравнения, возраст солнечной системы равен примерно 1.5*10^17 секунд.

GPU иногда дает фантастические результаты

это не тот случай )

[Smitt&Wesson]

А, что значит "прыгающих"? Может ещё и бьющих по-лбу?
Пятьдесят лет живу. Тридцать из них изучаю математику, чёт про такое не слышал. Просветите .

[Luuzuk]

в комментариях кода в первом же посте написано

[veniside]

это кривой термин из первого сообщения:

/*Если в числе все цифры не меньше стоящих слева от них, оно называется увеличивающимся. Пример - 133456.
Соответственно, если числа не меньше стоящих справа, оно называется убывающим. Пример: 66420.
Числа, которые не являются ни возрастающими, ни убывающими мы будет называть прыгающим.
Сколько существует прыгающих чисел, меньше 10^65?*/

[Smitt&Wesson]

Почитал коммнтарии. Башку сломал. Кто-нибудь может мне внятно сказать чего ТС хочет? Или мне жаргон 80-х применить? Думаю, мало не покажется.

[veniside]

если цифры в числе не убывают, то оно "увеличивающееся", например: 11112223445666789
если цифры в числе не возрастают, то оно "убывающее", например: 9988776665333211
если ни то, ни то, то оно "прыгающее", например: 1236321

вопрос: сколько существует разных "прыгающих" числел, в диапазоне от 0 до 10^65