یک زیر عدد از عدد طبیعی و مثبت x، یک زیررشتهی متوالی از ارقام x است. برای مثال، ۱۴۳ یک زیر عدد از ۱۱۴۳ است. اما ۹۲۱ یک زیر عدد از ۹۰۲۱۸ نیست. با این تعریف، یک عدد n رقمی n×(n+1)/2 زیر عدد (نه لزوما متمایز) دارد. ضمنا یک زیر عدد را معتبر میگوییم اگر با صفر شروع نشود.
فرض کنید P(x) تعداد زیر عددهای معتبر عدد x است که اول هم هستند. برای مثال P(130312) برابر ۶ است؛ زیرا از بین ۲۱ زیر عدد آن، تنها۱۷ تایش معتبرند (با صفر شروع نمیشوند) و از این ۱۷ تا، تنها ۶ تایش اول هستند که عبارتند از ۳،۲،۱۳،۳۱،۱۳۰۳ و ۳. دقت کنید که عدد ۳ دوبار شمرده شده است؛ یک بار برای زیر رشته شامل رقم دوم (از سمت چپ) و یک بار برای زیر رشته شامل رقم چهارم (از سمت چپ).
حاصل جمع خروجی تابع P روی تمام اعداد کوچکتر از ۱۳۸۹۰۰۰ (یعنی P(1)+P(2)+…+P(1389000)) را Mبگیرید. مقدار باقیماندهی تقسیم M بر Δ چند است؟
پاسخ ارائه شده در این سوال با فرض Δ=97987 محاسبه شده است.
پاسخ
40846