OFFSET
0,1
COMMENTS
Legend has it that the ArrayList data structure in Java would normally be initialized with ten array spaces. Then, if the ArrayList foresaw a need for more spaces, it would add more according to this formula: newCapacity = (oldCapacity * 3)/2 + 1; this was part of the ensureCapacity subroutine.
So, for example, when it became clear that the array would need to hold more than ten elements, it would expand the array to sixteen spaces. And once sixteen was not enough, 25, then 38 and so on and so forth.
Now the formula is newCapacity = oldCapacity + floor(oldCapacity/2) (the latter summand is expressed as oldCapacity shifted one bit to the right).
Whatever formula is used, what happens "under the hood" is that the array with oldCapacity number of spaces is moved to an array with newCapacity number of spaces.
This avoids having to constantly copy an entire array to a new location with more spaces just to add one space. The programmer using ArrayList can remain blissfully unaware that any moving is going on at all.
LINKS
Chris Ramacciotti, Unveiling the Mystery Behind a Java Abstraction, Treehouse blog, November 10, 2016.
FORMULA
a(0) = 6, a(n) = floor( 3*a(n-1)/2 ) + 1 for n > 0.
MAPLE
A[0]:= 6: for n from 1 to 100 do A[n]:= floor(3*A[n-1]/2)+1 od:
seq(A[i], i=0..100); # Robert Israel, Jun 04 2018
MATHEMATICA
NestList[Floor[3#/2] + 1 &, 6, 50]
PROG
(Java) for (int i = 10; i < Integer.MAX_VALUE/16; i = (3 * i)/2 + 1) { System.out.print(i + ", "); }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alonso del Arte, Apr 12 2018
STATUS
approved