חידת אלגוריתם מתמטי...

[עריסטו]

חידת אלגוריתם מתמטי...

נתון מספר טבעי n, יש למצוא את מספר הפתרונות של המשוואה x^2+y^2+z^2+w^2=n במספרים שלמים. למשל אם n=1 יש למשוואה שמונה פתרונות:

x,y,z,w = 0,0,0,1 0,0,0,-1 0,0,1,0 0,0,-1,0 0,1,0,0 0,-1,0,0 1,0,0,0 -1,0,0,0​

כמובן צריך למצוא אלגוריתם בעל סיבוכיות מינימלית. לצורך חישוב הסיבוכיות ניתן להניח שפעולת חשבון על מספר דורשת זמן קבוע שאינו תלוי בגודל המספר.

 

[ןן גיל ןן]

../images/Emo62.gif

מצאתי כאן את הנוסחה הבאה: In 1834, Carl Gustav Jakob Jacobi found an exact formula for the total number of ways a given positive integer n can be represented as the sum of four squares. This number is eight times the sum of the divisors of n if n is odd and 24 times the sum of the odd divisors of n if n is even מכאן- אם פשוט נעבור על כל המספרים בין 1 ל- n ונסכם את המחלקים הרצויים לנו נקבל סיבוכיות o zz. אם רוצים לשפר, אפשר להשתמש באלגוריתם לפירוק לגורמים ראשוניים של n, ומתוך הפירוק קל למצוא את סכום המחלקים ואת סכום המחלקים האיזוגיים.

 

[ןן גיל ןן]

הקישור שהתפספס

http://en.wikipedia.org/wiki/Lagrange's_four-square_theorem

 

[עריסטו]

../images/Emo127.gif התכוונת..

O של שורש n (כדי למצוא את מחלקי n מספיק לעבור על המספרים בין 1 לשורש n) דרך אגב ניתן לסכם את הנוסחה של יקובי כך: מספר הפתרונות הוא 8 פעמים סכום מחלקי n שאינם כפולה של 4.

 

[עריסטו]

הערה

ידוע שכל מספר טבעי הוא סכום ריבועיהם של ארבעה מספרים שלמים, כלומר לכל n טבעי יש למשוואה הנ"ל פתרון.

 

[מספר6]

עוד הערה

אפשר למצוא את מחלקי n בהרבה פחות זמן משורש n. http://en.wikipedia.org/wiki/Integer_factorization