কোলাৎজ অনুমান

থাম্ব|upright=0.6|ক্ষুদ্র সংখ্যাগুলোর কোলাৎজ ফাংশনে পরিভ্রমণ (গতিবিদ্যা)|পরিভ্রমণ প্রদর্শনকারী [[নির্দেশিত গ্রাফ, জোড় সংখ্যাগুলো বাদ দেওয়া হয়েছে। কোলাৎজ অনুকল্প বলে যে সকল পথ শেষে ১-এ পৌঁছায়।]]

কোলাৎজ অনুকল্প গণিতের সর্বাধিক বিখ্যাত অমীমাংসিত সমস্যাগুলোর একটি। এই অনুমানটি জিজ্ঞাসা করে যে দুটি সরল গাণিতিক প্রক্রিয়া বারংবার প্রয়োগের মাধ্যমে সকল ধনাত্মক পূর্ণসংখ্যাকেই কি শেষ পর্যন্ত ১-এ রূপান্তর করা সম্ভব? এটি পূর্ণসংখ্যার অনুক্রমগুলোর সাথে সম্পর্কিত, যেখানে প্রতিটি পদ পূর্ববর্তী পদ থেকে নিম্নরূপে পাওয়া যায়: কোনো পদ জোড় হলে, পরবর্তী পদ হবে তার অর্ধেক। পদটি বিজোড় হলে, পরবর্তী পদ হবে পূর্ববর্তী পদের তিন গুণের সাথে ১ যোগ। এই অনুমান অনুসারে যেকোনো ধনাত্মক পূর্ণসংখ্যা দিয়ে অনুক্রম শুরু করলেই তা শেষে ১-এ পৌঁছাবে। যেকোনো ধনাত্মক পূর্ণসংখ্যার জন্য এই অনুকল্পটি ২.৩৬ × ১০২১ পর্যন্ত যাচাই করা হয়েছে, তবে কোনো সাধারণ প্রমাণ এখনো পাওয়া যায়নি।

এটির নামকরণ করা হয়েছে গণিতবিদ লোথার কোলাৎজের নামে, যিনি ডক্টরেট পাওয়ার দুই বছর পর ১৯৩৭ সালে এই ধারণাটি প্রবর্তন করেন। সংশ্লিষ্ট সংখ্যাগুলির অনুক্রমকে কখনও কখনও হেইলস্টন অনুক্রম, শিলাবৃষ্টি সংখ্যা বা শিলাবৃষ্টি অঙ্ক (কারণ মানগুলো সাধারণত মেঘে শিলাবৃষ্টির মতো একাধিকবার উপরে-নিচে ওঠানামা করে) অথবা বিস্ময়কর সংখ্যা বলা হয়।

পল এর্ডশ কোলাৎজ অনুকল্প সম্পর্কে বলেছিলেন: "গণিত হয়তো এখনো এমন সমস্যাগুলোর জন্য প্রস্তুত নয়।" জেফ্রি লাগারিয়াস ২০১০ সালে উল্লেখ করেন যে কোলাৎজ অনুকল্প "একটি অসাধারণভাবে কঠিন সমস্যা, যা বর্তমান গণিতের সম্পূর্ণ আওতার বাইরে"। তবে, যদিও কোলাৎজ অনুকল্প নিজে অমীমাংসিত রয়ে গেছে, এটি সমাধানের প্রচেষ্টা নতুন কৌশল এবং অনেক আংশিক ফলাফলের জন্ম দিয়েছে।
সমস্যার বিবৃতি

থাম্ব|১ থেকে ৯৯৯৯ পর্যন্ত সংখ্যা এবং তাদের সংশ্লিষ্ট মোট থামার সময়
থাম্ব|১ থেকে ১০৮ সংখ্যাগুলোর মোট থামার সময়ের হিস্টোগ্রাম। অক্ষে মোট থামার সময়, অক্ষে পুনরাবৃত্তি সংখ্যা।
থাম্ব|১ থেকে ১০৯ সংখ্যাগুলোর মোট থামার সময়ের হিস্টোগ্রাম। অক্ষে মোট থামার সময়, অক্ষে পুনরাবৃত্তি সংখ্যা।
থাম্ব|২ থেকে ১০৭ ইনপুটের জন্য পুনরাবৃত্তি সময়।
alt=মোট থামার সময়: ২৫০, ১০০০, ৪০০০, ২০০০০, ১০০০০০, ৫০০০০০ পর্যন্ত সংখ্যা|থাম্ব|২৫০, ১০০০, ৪০০০, ২০০০০, ১০০০০০, ৫০০০০০ পর্যন্ত সংখ্যাগুলোর মোট থামার সময়

যেকোনো ধনাত্মক পূর্ণসংখ্যার উপর নিম্নলিখিত অপারেশনটি বিবেচনা করুন:

* সংখ্যাটি জোড় হলে তাকে দুই দিয়ে ভাগ করুন।
* সংখ্যাটি বিজোড় হলে তাকে তিন দিয়ে গুণ করে এক যোগ করুন।

মডুলার গাণিতিক নোটেশনে, ফাংশন কে নিম্নরূপে সংজ্ঞায়িত করা হয়:
f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2},\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}

যেকোনো ধনাত্মক পূর্ণসংখ্যা দিয়ে শুরু করে এই অপারেশনটি বারংবার প্রয়োগ করে একটি অনুক্রম গঠন করুন, যেখানে প্রতিটি ধাপের ফলাফল পরবর্তী ধাপের ইনপুট হিসেবে ব্যবহৃত হয়।

গণিতের ভাষায়:
a_i = \begin{cases}n & \text{for } i = 0, \\ f(a_{i-1}) & \text{for } i > 0 \end{cases}

কোলাৎজ অনুকল্পের মূল বক্তব্য: যেকোনো ধনাত্মক পূর্ণসংখ্যা দিয়ে শুরু করলেই এই প্রক্রিয়াটি শেষে সংখ্যা ১-এ পৌঁছাবে। অর্থাৎ, প্রতিটি n এর জন্য এমন কোনো i বিদ্যমান যেখানে a_i = 1।

অনুকল্পটি মিথ্যা হলে একমাত্র সম্ভব হবে যদি এমন কোনো প্রারম্ভিক সংখ্যা থাকে যা ১-বিহীন কোনো অনুক্রম তৈরি করে। এমন অনুক্রম হয় ১-বর্জিত কোনো পুনরাবৃত্ত চক্রে প্রবেশ করবে, অথবা সীমাহীনভাবে বৃদ্ধি পাবে। এখন পর্যন্ত এমন কোনো অনুক্রম পাওয়া যায়নি।

ক্ষুদ্রতম যার জন্য হয়, তাকে এর থামার সময় (stopping time) বলা হয়। অনুরূপভাবে, ক্ষুদ্রতম যার জন্য হয়, তাকে এর মোট থামার সময় (total stopping time) বলা হয়। যদি বা এর কোনোটি বিদ্যমান না থাকে, তবে আমরা বলি থামার সময় বা মোট থামার সময় যথাক্রমে অসীম।

কোলাৎজ অনুকল্প দাবি করে যে প্রতিটি এর মোট থামার সময় সসীম। এটি এই কথারও সমতুল্য যে প্রতিটি এর একটি সসীম থামার সময় আছে।

যেহেতু বিজোড় হলে সর্বদা জোড় হয়, তাই কোলাৎজ ফাংশনের একটি "শর্টকাট" রূপ ব্যবহার করা যেতে পারে:
f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \pmod{2},\\ \frac{3n+1}{2} & \text{if } n\equiv 1 \pmod{2}. \end{cases}
এই সংজ্ঞাটি প্রক্রিয়ার সামগ্রিক গতিবিদ্যা পরিবর্তন না করেই থামার সময় ও মোট থামার সময়ের মান হ্রাস করে।
লব্ধ তথ্য

উদাহরণস্বরূপ, দিয়ে শুরু করে এবং "শর্টকাট" ছাড়া ফাংশন প্রয়োগ করলে অনুক্রমটি পাওয়া যায়: ।

সংখ্যাটি ১-এ পৌঁছাতে বেশি সময় নেয়: ।


এর অনুক্রমটি নীচে তালিকাভুক্ত ও গ্রাফে দেখানো হয়েছে (বিজোড় সংখ্যাগুলো গাঢ় করে), যা ১-এ পৌঁছাতে ১১১ ধাপ নেয় (৪১ ধাপ বিজোড় সংখ্যার মাধ্যমে) এবং সর্বোচ্চ ৯২৩২ পর্যন্ত বৃদ্ধি পেয়ে অবশেষে ১-এ নামে।

:


যেসব প্রারম্ভিক মানের মোট থামার সময় তাদের থেকে ছোট যেকোনো প্রারম্ভিক মানের চেয়ে বেশি, তাদের অনুক্রম শুরু হয়:
:১, ২, ৩, ৬, ৭, ৯, ১৮, ২৫, ২৭, ৫৪, ৭৩, ৯৭, ১২৯, ১৭১, ২৩১, ৩১৩, ৩২৭, ৬৪৯, ৭০৩, ৮৭১, ১১৬১, ২২২৩, ২৪৬৩, ২৯১৯, ৩৭১১, ৬১৭১, ... ।

যেসব প্রারম্ভিক মানের সর্বোচ্চ ট্র্যাজেক্টরি বিন্দু যেকোনো ছোট প্রারম্ভিক মানের চেয়ে বেশি, সেগুলো হলো:
:১, ২, ৩, ৭, ১৫, ২৭, ২৫৫, ৪৪৭, ৬৩৯, ৭০৩, ১৮১৯, ৪২৫৫, ৪৫৯১, ৯৬৬৩, ২০৮৯৫, ২৬৬২৩, ৩১৯১১, ৬০৯৭৫, ৭৭৬৭১, ১১৩৩৮৩, ১৩৮৩৬৭, ১৫৯৪৮৭, ২৭০২৭১, ৬৬৫২১৫, ৭০৪৫১১, ...

থেকে ১-এ পৌঁছানোর ধাপ সংখ্যা:
:০, ১, ৭, ২, ৫, ৮, ১৬, ৩, ১৯, ৬, ১৪, ৯, ৯, ১৭, ১৭, ৪, ১২, ২০, ২০, ৭, ৭, ১৫, ১৫, ১০, ২৩, ১০, ১১১, ১৮, ১৮, ১৮, ১০৬, ৫, ২৬, ১৩, ১৩, ২১, ২১, ২১, ৩৪, ৮, ১০৯, ৮, ২৯, ১৬, ১৬, ১৬, ১০৪, ১১, ২৪, ২৪, ...

সর্বাধিক মোট থামার সময়সহ প্রারম্ভিক মান
*(নির্দিষ্ট সীমার মধ্যে):
**১০-এর কম: ৯ (১৯ ধাপ)
**১০০-এর কম: ৯৭ (১১৮ ধাপ)
**১০০০-এর কম: ৮৭১ (১৭৮ ধাপ)
**১০৪-এর কম: ৬১৭১ (২৬১ ধাপ)
**১০৫-এর কম: (৩৫০ ধাপ)
**১০৬-এর কম: (৫২৪ ধাপ)
**১০৭-এর কম: (৬৮৫ ধাপ)
**১০৮-এর কম: (৯৪৯ ধাপ)
**১০৯-এর কম: (৯৮৬ ধাপ)
**১০১০-এর কম: (১১৩২ ধাপ)
**১০১১-এর কম: (১২২৮ ধাপ)
**১০১২-এর কম: (১৩৪৮ ধাপ)

এই সংখ্যাগুলো নির্দিষ্ট ধাপ সংখ্যার জন্য সর্বনিম্ন মান, তবে প্রদত্ত সীমার মধ্যে একমাত্র নয়। যেমন, এরও এর মতো ১১৩২ ধাপ আছে।

ডিজিট সংখ্যার (বাইনারি) সাপেক্ষে সর্বনিম্ন মোট থামার সময় বিশিষ্ট প্রারম্ভিক মানগুলি হলো দুটির ঘাত (powers of two), যেহেতু কে ১-এ পৌঁছাতে বার অর্ধেক করা হয় এবং এটি কখনও বৃদ্ধি পায় না।
দৃশ্যায়ন


File:Collatz orbits of the all integers up to 1000.svg|প্রথম ১০০০ সংখ্যার কক্ষপথ দেখানো নির্দেশিত গ্রাফ।
File:CollatzConjectureGraphMaxValues.jpg|x অক্ষ মূলত শুরুর সংখ্যা প্রতিনিধিত্ব করে, y অক্ষ ১-এ পৌঁছানোর শৃঙ্খল চলাকালীন সর্বোচ্চ সংখ্যা প্রতিনিধিত্ব করে। এই প্লটটি একটি সীমাবদ্ধ y অক্ষ দেখায়: কিছু x মান 2.7\times10^7 পর্যন্ত উচ্চ মধ্যবর্তী মান উৎপন্ন করে (x = ৯৬৬৩ এর জন্য)
File:Collatz-max.png|পূর্ববর্তী প্লটের মতোই কিন্তু লগ স্কেলে, তাই সমস্ত y মান দেখানো হয়েছে। প্লটের মাঝখানে প্রথম মোটা রেখাটি ২৭ থেকে শুরু হওয়া শৃঙ্খলের সাথে সম্পর্কিত, যা ৯২৩২-এ সর্বোচ্চে পৌঁছায়।
File:All Collatz sequences of a length inferior to 20.svg|২০ এর চেয়ে কম ধাপযুক্ত সমস্ত সংখ্যার গাছ।
File:Collatz Conjecture 100M.jpg|alt=কোলাৎজ অনুমান 100M|প্রথম ১০০ মিলিয়ন সংখ্যার জন্য একে পৌঁছাতে যে সংখ্যক পুনরাবৃত্তি লাগে।
File:Collatz_conjecture_tree_visualization.png|১ মিলিয়নের নিচে ৫০০০ টি র‍্যান্ডম শুরুর বিন্দুর জন্য কোলাৎজ অনুমান পথ।

টীকা
তথ্যসূত্র
আরও দেখুন

বিষয়শ্রেণী:সংখ্যাতত্ত্বের অমীমাংসিত সমস্যা