پرش به محتوا

رویه کاپرکار

از ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه اعداد، رَویِّه کاپرِکار (Kaprekar's Routine)، یک الگوریتم تکراری است که در هر تکرار خود عددی طبیعی در مبنای خاصی را گرفته و از روی آن با مرتب‌سازی ارقامش به دو حالت ترتیب صعودی و نزولی، دو عدد جدید ایجاد کرده که تفاضلشان، عددی را به‌وجود می‌آورد که در تکرار بعدی الگوریتم مجدد مورد استفاده قرار می‌گیرد. این رویه را به نام ریاضی‌دان هندی مخترع آن، دی. آر. کاپرکار نامگذاری نموده‌اند.

کاپرِکار نشان داد که درحالت ۴-رقمی، اگر عدد آغازین دارای حداقل دو رقم متمایز باشد، همیشه پس از گذشت ۷ تکرار عدد ۶۱۷۴ تولید می‌گردد که اکنون به آن ثابت کاپرِکار گفته می‌شود.[۱]

تعریف و خواص

[ویرایش]

این الگوریتم به صورت زیر است:[۲]

  1. یک عدد طبیعی چون در مبنای انتخاب کنید. این عدد اولین عدد دنباله خواهد بود.
  2. بامرتب سازی ارقام به صورت نزولی عدد جدید و با مرتب‌سازی ارقام به صورت صعودی عدد جدید بدست می‌آیند. این اعداد ممکن است دارای ارقام پیشروی صفر باشند که در این صورت نادیده انگاشته خواهند شد (که البته می‌توان آن‌ها را حفظ کرد). از تفاضل عدد بعدی دنبال بدست خواهد آمد.
  3. مرحله ۲ را تکرار کنید.

به این دنباله، دنباله کاپرکار گفته شده و تابع نیز نگاشت کاپرکار نام دارد. برخی از اعداد به خودشان نگاشته می‌شوند؛ این اعداد نقاط ثابت نگاشت کاپرکار بوده[۳] و به آن‌ها ثوابت کاپرکار می‌گویند. برای تمام پایه‌های ، صفر یک ثابت کاپرکار است و لذا به آن ثابت بدیهی کاپرکار گفته می‌شود. سایر ثوابت کاپرکار را ثوابت نابدیهی کاپرکار گویند.

به عنوان مثال در مبنای ۱۰ با شروع از ۳۵۴۲ داریم:

که در آن ۶۱۷۴ یک ثابت کاپرکار است.

ارجاعات

[ویرایش]
  1. Hanover 2017, p. 1, Overview.
  2. Hanover 2017, p. 3, Methodology.
  3. (دنباله A099009 در OEIS)

منابع

[ویرایش]
  • Hanover, Daniel (2017). "The Base Dependent Behavior of Kaprekar's Routine: A Theoretical and Computational Study Revealing New Regularities". International Journal of Pure and Applied Mathematics. arXiv:1710.06308.