Sunday, May 28, 2006


I drew spiral sunflowers (think i*a mod n for various i) this morning thinking of a problem that led me to formulate the following:

Given a partition of integers [0,n-1] into 2 lists A and B, check if for each i in A, for all j for which i+j mod n is in B, we have that i-j mod n is in A.

A subquadratic algorithm will be a start.


Anonymous Anonymous said...

I interpret your condition as saying "BAB" is a forbidden arithmetic subsequence, where the first and last B may be the same item. Then I think B must be either the empty set, or a translate of {0, d, 2d, ...}, where d is an odd divisor of n.

For example if n=18, the only possible B sets are them empty set, the 9 translates of {0, 9}, the 3 translates of {0, 3, 6, 9, 12, 15}, and the whole set.

That should be linear time testable.

9:13 AM  
Anonymous Anonymous said...

What a great site, how do you build such a cool site, its excellent.

12:36 AM  

Post a Comment

<< Home