Разложение числа на слагаемы

From

Max Alekseyev (2:5015/60)

To

Anton Yurchenko

Date

2002-10-28T22:04:18Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Anton !

Replying to a message of Anton Yurchenko to All:

 AY>  Есть целое N (порядка 1000), необходимо все целые числа из 1..N
 AY> представить в виде суммы не более чем двух чисел (то есть можно и
 AY> одним, 7=3+4 и 7=7 - оба корректны). При этом число этих "простейших"
 AY> слагаемых должно быть минимально.

Это частный случай The Postage Stamp Problem для h=2.

Вот пара ссылок:
http://www.ams.org/journal-getitem?pii=S0025-5718-99-01204-1
http://erdos.math.swt.edu/teach/2000/fall/5336/projects/projectall.pdf

В последней статье приводится результат:

2/7 k^2 <= n(2,k) <= (1-0.1329) k^2/2

Из которого следует:
для N=100 оптимально число "слагаемых" s удовлетворяет неравенству 16<=s<=19
для N=1000 соответственно 49<=s<=60

 AY>  Например для N=100 этот набор
 AY> может состоять из 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90  (но
 AY> чую что это не оптимально...)

Восемнадцать слагаемых не противоречит указанному выше неравенству ;-)

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)