Sep. 5th, 2007

Update к

Sep. 5th, 2007 09:53 pm
avzel: (Default)
http://avzel.livejournal.com/9738.html. Напомню, что речь шла о следующей задачке: построить явно (т.е. нерекурсивно) последовательность f(0), f(1), f(2), ... целых положительных чисел, такую, что отображение n \mapsto f(n)/f(n-1) является биекцией множества положительных целых чисел на множество всех положительных рациональных чисел. Ответ (не единственный, надо полагать): определим f(n) как число разбиений числа n в сумму степеней двойки, таких что каждая степень двойки берется не более двух раз. Например, f(10) = 5, так как 10= 8 + 2 = 8 + 1 + 1 = 4 + 4 + 2 = 4 + 4 + 1 + 1 = 4 + 2 + 2 + 1 + 1. Я нашел эту задачу в http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/August2007.html, где она сформулирована в "перевернутом" виде, т.е., дано выражение для f(n), и требуется найти мультимножество значений f(n)/f(n-1). Доказательство, что эта функция обладает искомым свойством, можно прочитать в http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/August2007.html. Я придумал другое доказательство, основанное на том, что f(n)/f(n-1) можно явным образом представить в виде цепной дроби, которая считывается с двоичного разложения числа n. Мне непонятно, как люди из IBM Research наткнулись на эту замечательную функцию. Интересно, можно ли её придумать как решение задачи в моей постановке.

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627 282930
31      

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 24th, 2017 04:52 am
Powered by Dreamwidth Studios