Algorithms/Smith number

عدد سميث Smith Number هو عدد مركّب تكون مجموع أرقامه مساوية لمجموع الأرقام في عوامله الأولية.

مثال:

المدخلات : n = 4
المخرجات : يوجد
العوامل الأولية = 2, 2 و 2 + 2 = 4
العدد 4 من أعداد سميث

المدخلات : n = 6
المخرجات : لا يوجد
العوامل الأولية = 2, 3 و 2 + 3 لا يساوي 6
العدد 6 ليس من أعداد سميث

المدخلات : n = 666
المخرجات : يوجد
العوامل الأولية = 2, 3, 3, 37 و 2 + 3 + 3 + (3 + 7) = 6 + 6 + 6 = 18
العدد 666 من أعداد سميث

المدخلات : n = 13
المخرجات : لا يوجد
العوامل الأولية = 13 و 13 = 13
ولكن 13 ليس من أعداد سميث لأنّه ليس عددًا مركّبًا

تنفيذ الخوارزمية

تقوم الخوارزمية على فكرة العثور على جميع الأعداد الأولية تحت حدّ معين باستخدام منخل سوندارام Sieve of Sundaram (وهذا مفيد إذا كنا نرغب في التحقق من أن مجموعة من الأعداد هي من أعداد سميث أم لا). بعد ذلك يجري التحقق من كون كلّ رقم في المدخلات وذلك بحساب جميع العوامل الأولية لذلك العدد وحساب مجموع الأرقام لكل عامل أولي، إلى جانب حساب مجموع الأرقام في العدد المعطى، وفي النهاية تجري مقارنة المجموعين، فإن كانا متشابهين كان العدد من أعداد سميث.

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<bits/stdc++.h> 
using namespace std; 
const int MAX = 10000; 

// تستخدم هذه المصفوفة لتخزين جميع الأرقام الأولية التي تكون أصغر من العدد ‎10^6
vector <int> primes; 

// دالة مساعدة لتنفيذ خوارزمية منخل سوندارام
void sieveSundaram() 
{ 
	// (2*x + 2) ينتج منخل سوندارام عمومًا أعدادًا أولية أصغر من
	// x للعدد المعطى
	// MAX ولمّا كنا نريد الأعداد الأولية التي تكون أصغر من 
	// فإننا سنقلل الحد الأعلى إلى النصف
	// تستخدم هذه المصفوفة للفصل بين الأعداد ذات الصيغة
	// i+j+2ij
	// والأعداد التي تحقق العلاقة
	// 1 <= i <= j
	bool marked[MAX/2 + 100] = {0}; 

	// هذه العملية هي جوهر خوارزمية منخل سونادرام
	// تعليم جميع الأرقام التي لا تنتج أعدادًا أولية وذلك بتنفيذ
	for (int i=1; i<=(sqrt(MAX)-1)/2; i++) 
		for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) 
			marked[j] = true; 

	// لمّا كان العدد 2 عددًا أوليًا
	primes.push_back(2); 

	// طباعة الأعداد الأولية الأخرى. تأتي الأعداد الأولية الباقية من العملية
	// 2*i + 1
	// بشرط أن يكون العدد الحالي غير معلّمً
	for (int i=1; i<=MAX/2; i++) 
		if (marked[i] == false) 
			primes.push_back(2*i + 1); 
} 

// تعيد الدالة قيمة صحيحة إن كان العدد المعطى من أعداد سميث، وتعيد قيمة خاطئة فيما عدا ذلك
bool isSmith(int n) 
{ 
	int original_no = n; 

	// حساب مجموع الأرقام في العوامل الأولية للعدد المعطى
	int pDigitSum = 0; 
	for (int i = 0; primes[i] <= n/2; i++) 
	{ 
		while (n % primes[i] == 0) 
		{ 
			// إن كان العدد الأولي الحالي من العوامل الأولية
			// pDigitSum نضيف أعداده إلى 
			int p = primes[i]; 
			n = n/p; 
			while (p > 0) 
			{ 
				pDigitSum += (p % 10); 
				p = p/10; 
			} 
		} 
	} 

	// إن لم تكن قيمة العدد المعطى قد أصبحت مساوية للعدد 1
	// فهذا يعني أن عاملًا أوليًا واحدًا قد تبقى ويجب جمعه
	
	if (n != 1 && n != original_no) 
	{ 
		while (n > 0) 
		{ 
			pDigitSum = pDigitSum + n%10; 
			n = n/10; 
		} 
	} 

	// تم حساب جميع الأرقام في العوامل الأولية
	// والآن يجري حساب الأرقام في العدد الأصلي
	int sumDigits = 0; 
	while (original_no > 0) 
	{ 
		sumDigits = sumDigits + original_no % 10; 
		original_no = original_no/10; 
	} 

	// إن كان مجموع الأرقام في الأعداد الأولية
	// ومجموع الأرقام في العدد الأصلي متساويين
	// تعيد الدالة قيمة صحيحة، وتعيد قيمة خاطئة فيما عدا ذلك
	return (pDigitSum == sumDigits); 
} 

// اختبار الشيفرة السابقة
int main() 
{ 
// العثور على جميع الأعداد الأولية قبل الحدّ المعرّف أعلاه
// تستخدم هذه الأعداد في العثور على العوامل الأولية
sieveSundaram(); 

cout << "Printing first few Smith Numbers"
		" using isSmith()n"; 
for (int i=1; i<500; i++) 
	if (isSmith(i)) 
		cout << i << " "; 
	return 0; 
}

• بايثون:

import math 

MAX = 10000

# تخزّن هذه القائمة جميع الأرقام الأولية التي تكون أصغر من العدد ‎10^6
primes = [] 

# دالة مساعدة لتنفيذ خوارزمية منخل سونادرام
def sieveSundaram (): 
	# (2*x + 2) ينتج منخل سوندارام عمومًا أعدادًا أولية أصغر من
	# x للعدد المعطى
	# MAX ولمّا كنا نريد الأعداد الأولية التي تكون أصغر من 
	# فإننا سنقلل الحد الأعلى إلى النصف
	# تستخدم هذه المصفوفة للفصل بين الأعداد ذات الصيغة
	# i+j+2ij
	# والأعداد التي تحقق العلاقة
	# 1 <= i <= j
	marked = [0] * ((MAX/2)+100) 
	
	# هذه العملية هي جوهر خوارزمية منخل سونادرام
	# تعليم جميع الأرقام التي لا تنتج أعدادًا أولية وذلك بتنفيذ
	i = 1
	while i <= ((math.sqrt (MAX)-1)/2) : 
		j = (i* (i+1)) << 1
		while j <= MAX/2 : 
			marked[j] = 1
			j = j+ 2 * i + 1
		i = i + 1
	# لما كان العدد 2 عددًا أوليًا
	primes.append (2) 
	
	# طباعة الأعداد الأولية الأخرى، أما الأعداد الأولية المتبقية
	# 2*i + 1 فتأتي من العملية
	# بشرط أن يكون العدد الحالي غير معلّم
	i=1
	while i <= MAX /2 : 
		if marked[i] == 0 : 
			primes.append( 2* i + 1) 
		i=i+1


# تعيد هذه الدالة قيمة صحيحة إن كان العدد المعطى من أعداد سميث، وإلا فإنّها تعيد قيمة خاطئة
def isSmith( n) : 
	original_no = n 
	
	# حساب مجموع الأرقام في العوامل الأولية للعدد المعطى
	pDigitSum = 0; 
	i=0
	while (primes[i] <= n/2 ) : 
		
		while n % primes[i] == 0 : 
			#If primes[i] is a prime factor , 
			# add its digits to pDigitSum. 
			p = primes[i] 
			n = n/p 
			while p > 0 : 
				pDigitSum += (p % 10) 
				p = p/10
		i=i+1
	
	# إن لم تصبح قيمة العدد المعطى مساوية للعدد 1 فهذا يعني وجود
	# عامل أولي يجب جمعه كذلك
	if not n == 1 and not n == original_no : 
		while n > 0 : 
			pDigitSum = pDigitSum + n%10
			n=n/10
		
	# حصلنا على مجموع الأرقام في العوامل الأولية
	# والآن نحسب مجموع الأرقام في العدد الأصلي
	sumDigits = 0
	while original_no > 0 : 
		sumDigits = sumDigits + original_no % 10
		original_no = original_no/10
		
	# إن تساوى مجموع الأرقام في العوامل الأولية مع مجموع الأرقام
	# في العدد الأصلي، فإنّ الدالة تعيد قيمة صحيحة
	# وإلا فإنها ستعيد قيمة خاطئة
	return pDigitSum == sumDigits 

# اختبار الدوال السابقة
# إيجاد جميع الأعداد الأولية قبل الحد المعطى
# تستخدم هذه الأعداد في حساب العوامل الأولية
sieveSundaram(); 
print "Printing first few Smith Numbers using isSmith()"
i = 1
while i<500 : 
	if isSmith(i) : 
		print i, 
	i=i+1

• جافا:

import java.util.Vector; 

class Test 
{ 
	
	static int MAX = 10000; 
	
	// تستخدم هذه المصفوفة لتخزين جميع الأرقام الأولية التي تكون أصغر من العدد ‎10^6
	static Vector <Integer> primes = new Vector<>(); 
	
	// دالة مساعدة لتنفيذ خوارزمية منخل سوندارام 
	static void sieveSundaram() 
	{ 
		// (2*x + 2) ينتج منخل سوندارام عمومًا أعدادًا أولية أصغر من
		// x للعدد المعطى
		// MAX ولمّا كنا نريد الأعداد الأولية التي تكون أصغر من 
		// فإننا سنقلل الحد الأعلى إلى النصف
		// تستخدم هذه المصفوفة للفصل بين الأعداد ذات الصيغة
		// i+j+2ij
		// والأعداد التي تحقق العلاقة
		// 1 <= i <= j
		boolean marked[] = new boolean[MAX/2 + 100]; 
	
		// هذه العملية هي جوهر خوارزمية منخل سونادرام
		// 2*i+1 تعليم جميع الأرقام التي لا تنتج أعدادًا أولية وذلك بتنفيذ  
		for (int i=1; i<=(Math.sqrt(MAX)-1)/2; i++) 
			for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) 
				marked[j] = true; 
	
		// لمّا كان العدد 2 عددًا أوليًا 
		primes.addElement(2); 
	
		// طباعة الأعداد الأولية الأخرى. تأتي الأعداد الأولية الباقية من العملية
		// 2*i + 1
		// بشرط أن يكون العدد الحالي غير معلّمً
		for (int i=1; i<=MAX/2; i++) 
			if (marked[i] == false) 
				primes.addElement(2*i + 1); 
	} 
	
	// تعيد الدالة قيمة صحيحة إن كان العدد المعطى من أعداد سميث، وتعيد قيمة خاطئة فيما عدا ذلك 
	static boolean isSmith(int n) 
	{ 
		int original_no = n; 
	
		//  حساب مجموع الأرقام في العوامل الأولية للعدد المعطى 
		int pDigitSum = 0; 
		for (int i = 0; primes.get(i) <= n/2; i++) 
		{ 
			while (n % primes.get(i) == 0) 
			{ 
				// إن كان العدد الأولي الحالي من العوامل الأولية
				//  pDigitSum نضيف أعداده إلى 
				int p = primes.get(i); 
				n = n/p; 
				while (p > 0) 
				{ 
					pDigitSum += (p % 10); 
					p = p/10; 
				} 
			} 
		} 
	
		// إن لم تكن قيمة العدد المعطى قد أصبحت مساوية للعدد 1
		// فهذا يعني أن عاملًا أوليًا واحدًا قد تبقى ويجب جمعه 
		if (n != 1 && n != original_no) 
		{ 
			while (n > 0) 
			{ 
				pDigitSum = pDigitSum + n%10; 
				n = n/10; 
			} 
		} 
	
		// تم حساب جميع الأرقام في العوامل الأولية
		// والآن يجري حساب الأرقام في العدد الأصلي 
		int sumDigits = 0; 
		while (original_no > 0) 
		{ 
			sumDigits = sumDigits + original_no % 10; 
			original_no = original_no/10; 
		} 
	
		/// إن كان مجموع الأرقام في الأعداد الأولية
		// ومجموع الأرقام في العدد الأصلي متساويين
		// تعيد الدالة قيمة صحيحة، وتعيد قيمة خاطئة فيما عدا ذلك 
		return (pDigitSum == sumDigits); 
	} 
	
	// اختبار الشيفرة السابقة 
	public static void main(String[] args) 
	{ 
		// العثور على جميع الأعداد الأولية قبل الحدّ المعرّف أعلاه
		// تستخدم هذه الأعداد في العثور على العوامل الأولية 
		sieveSundaram(); 
		
		System.out.println("Printing first few Smith Numbers" + 
						" using isSmith()"); 
		
		for (int i=1; i<500; i++) 
		if (isSmith(i)) 
			System.out.print(i + " "); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

Printing first few Smith Numbers using isSmith()
4 22 27 58 85 94 121 166 202 265 274 319 346 355 378 382 391 438 454 483

مصادر

• صفحة Smith Number في توثيق الخوارزميات في موقع GeeksforGeeks.