Motzkin numbers: Difference between revisions

<syntaxhighlight>

import java.math.BigInteger;

import java.text.NumberFormat;

import java.util.ArrayList;

import java.util.List;

import java.util.Locale;

public final class MotzkinNumbers {

public static void main(String[] aArgs) {

final int count = 42;

List<BigInteger> motzkins = motzkinNumbers(count);

NumberFormat ukNumberFormat = NumberFormat.getInstance(Locale.UK);

System.out.println(" n Motzkin[n]");

System.out.println("-----------------------------");

for ( int n = 0; n < count; n++ ) {

BigInteger motzkin = motzkins.get(n);

boolean prime = motzkin.isProbablePrime(PROBABILITY);

System.out.print(String.format("%2d %23s", n, ukNumberFormat.format(motzkin)));

System.out.println( prime ? " prime" : "" );

}

}

private static List<BigInteger> motzkinNumbers(int aSize) {

List<BigInteger> result = new ArrayList<BigInteger>(aSize);

result.add(BigInteger.ONE);

result.add(BigInteger.ONE);

for ( int i = 2; i < aSize; i++ ) {

BigInteger nextMotzkin = result.get(i - 1).multiply(BigInteger.valueOf(2 * i + 1))

.add(result.get(i - 2).multiply(BigInteger.valueOf(3 * i - 3)))

.divide(BigInteger.valueOf(i + 2));

result.add(nextMotzkin);

}

return result;

}

private static final int PROBABILITY = 20;

}

</syntaxhighlight>

{{ out }}

<pre>

n Motzkin[n]

-----------------------------

0 1

1 1

2 2 prime

3 4

4 9

5 21

6 51

7 127 prime

8 323

9 835

10 2,188

11 5,798

12 15,511 prime

13 41,835

14 113,634

15 310,572

16 853,467

17 2,356,779

18 6,536,382

19 18,199,284

20 50,852,019

21 142,547,559

22 400,763,223

23 1,129,760,415

24 3,192,727,797

25 9,043,402,501

26 25,669,818,476

27 73,007,772,802

28 208,023,278,209

29 593,742,784,829

30 1,697,385,471,211

31 4,859,761,676,391

32 13,933,569,346,707

33 40,002,464,776,083

34 114,988,706,524,270

35 330,931,069,469,828

36 953,467,954,114,363 prime

37 2,750,016,719,520,991

38 7,939,655,757,745,265

39 22,944,749,046,030,949

40 66,368,199,913,921,497

41 192,137,918,101,841,817

</pre>