ipsin.org

If you’re curious, here is a larger list of strings that have a hashCode() of 0 in java. (compressed with 7zip)

Having previously read about hash collision attacks, it occurred to me that it was not trivial to generate collisions.

In particular, I’m looking for strings that have a hashCode() of 0, since this can cause the JVM to re-compute the hash.

What do colliding alphanumeric Strings look like in java? Here’s a sample.

ARbyguv ARbygvW ARbygw8 ARbyhVv ARbyhWW ARbyhX8 ARbyi7v ARbyi8W ARbyi98 ARcZguv ARcZgvW ARcZgw8 ARcZhVv ARcZhWW ARcZhX8 ARcZi7v ARcZi8W ARcZi98 ASCyguv ASCygvW ASCygw8 ASCyhVv ASCyhWW ASCyhX8 ASCyi7v ASCyi8W ASCyi98 ASDZguv ASDZgvW ASDZgw8 ASDZhVv ASDZhWW

Amit Patel’s article on procedural map generation is a real gem.

It even includes a flash application for creating your own procedural maps.

In one article he manages to tie together:

• Voroni diagrams
• Lloyd’s algorithm and Poisson disk sampling
• Delaunay triangulation
• Perlin noise and Simplex noise

It’s part of a larger body of useful game programming links he maintains on his site.

Given an ordered string T of unique elements, consider an operation that takes k elements and permutes them randomly.

If you consider all the permutations of T, and you categorize them according to the minimum number of operations required to reach T, how many permutations are in each grouping?

For example, ABC, where an operation is swapping 2 elements:
0 operations: ABC (1 permutation)
1 operation: BAC, CBA, ACB (3 permutations)
2 operations: CAB, BCA (2 permutations)

So we could write this as

Swap 2

• n= 2: 1,3,2

So what do these groupings look like?

Swap 2

• n= 2: 1,1
• n= 3: 1,3,2
• n= 4: 1,6,11,6
• n= 5: 1,10,35,50,24
• n= 6: 1,15,85,225,274,120
• n= 7: 1,21,175,735,1624,1764,720
• n= 8: 1,28,322,1960,6769,13132,13068,5040

h3.Swap 3

• n= 3: 1,5
• n= 4: 1,14,9
• n= 5: 1,30,89
• n= 6: 1,55,439,225
• n= 7: 1,91,1519,3429
• n= 8: 1,140,4214,24940,11025
• n= 9: 1,204,10038,122156,230481

h3.Swap 4

• n= 4: 1,23
• n= 5: 1,75,44
• n= 6: 1,190,529
• n= 7: 1,406,4633
• n= 8: 1,770,27341,12208
• n= 9: 1,1338,118173,243368

Swap 5

• n= 5: 1,119
• n= 6: 1,454,265
• n= 7: 1,1330,3709
• n= 8: 1,3234,37085
• n= 9: 1,6882,355997

Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first n rows of a Stern-Brocot tree.

It’s surprisingly simple. To generate the first n+1 rows, take the values

where

given

where

for odd j and non-negative v_i.

Put informally, v_i is the number of trailing zeroes in the binary representation of i.

What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.