mystery sequence (easy?)

[Peter Pein]

N. J. A. Sloane schrieb:
> Dear Seqfans:
> 
> Can anyone figure this out?
> 
> %I A109636
> %S A109636 2,3,9,10,27,28,30,81,84,88,90,100,104,243,252,264,270,272,280,300,304,
> %T A109636 312,729,736,756,784,792,810,816,840,880,900,912,928,936,992,1000,1040,
> %U A109636 2187,2208,2268,2352,2368,2376
> %N A109636 Minimal numbers in k-almost prime numbers massiv of (n,k) such that number of (n,k+l) is equal 2^l times the number of (n,k) for any l>0.
> %H A109636 Wikipedia, <a href="http://en.wikipedia.org/wiki/Almost_prime">k-almost prime numbers</a>.
> %Y A109636 Cf. A000040, A001358, A014612, A014613, A014614.
> %Y A109636 Sequence in context: A047358 A003140 A057234 this_sequence A057236 A063257 A103039
> %Y A109636 Adjacent sequences: A109633 A109634 A109635 this_sequence A109637 A109638 A109639
> %K A109636 nonn,uned,obsc
> %O A109636 1,1
> %A A109636 Yury V. Shlapak (shlapak(AT)imp.kiev.ua), Aug 04 2005
> 
> Possibly one of the Russian-speaking members of the list can
> help by translating it to Russian, where it might be clearer?
> What does "(n,k)" mean???
> 
> Neil
> 
> PS The "binary splitting" mystery sequence A126119 of the other day remains
> a mystery
> 
> 

If you wite the k-almost primes in rows (one row for each k), you'll observe
that there exist P_{k_0}(n) with P_{k_0+1}(n)=2P_{k_0}(n). For each k>=k0:
P_{k+1}(n)=2P_{k}(n). A109636 is the sequence of the P_{k0}(n). In other
words: In the columns the values double from row k0 on.

Well, english isn't my mother toungue too.

Mathematica-speaking members might be able to translate this to better english:

A109636list[n_] :=
  Module[{p  = Prime[Range[n]], pal},
   pal = Transpose /@ Partition[
    NestList[Take[Union[Flatten[Outer[Times, #1, p]]], Length[#1]] & , p, n],
   2, 1]},
   Complement @@ Transpose[Cases[pal, {k_, kk_} /; kk == 2*k, {2}]]]


Timing[A109636list[100]]
-->
{2.125*Second,
 {2, 3, 9, 10, 27, 28, 30, 81, 84, 88, 90, 100, 104, 243, 252, 264, 270,
  272, 280, 300, 304, 312, 729, 736, 756, 784, 792, 810, 816, 840, 880, 900,
  912, 928, 936, 992, 1000, 1040, 2187, 2208, 2268, 2352, 2368, 2376, 2430,
  2448, 2464, 2520, 2624, 2640, 2700, 2720, 2736, 2752, 2784, 2800, 2808,
  2912, 2976, 3000, 3008, 3040, 3120, 6561, 6624, 6784, 6804, 7056, 7104,
  7128, 7290, 7344, 7360, 7392, 7552, 7560, 7616, 7744, 7808, 7840, 7872,
  7920, 8100, 8160, 8208, 8256, 8352, 8400, 8424, 8512, 8576, 8736, 8800,
  8928, 9000, 9024, 9088, 9120, 9152, 9280}
}

Peter





well, I guess I will leave it in the OEIS, now that both Alex and Peter
have worked on it!

Thanks for all your help!

I will revise the entry over the next few days

Neil



Dear Mathfun, Seqfans:

Numbers of set systems of various types
---------------------------------------

There are some sequences that may be missing from the OEIS,
in case somebody would be interested in calculating them.

This was suggested by reading pages 1 and 2 of the book by Heinz Koenig on
Measure and Integration (Springer, 1997)

We are considering a "set system" S,
which is a nonempty collection of subsets 
A of a set X, where X has n points.  There will be two
versions of each sequence, depending on whether the
points are labeled or unlabeled.

We define several properties which S might have:

U : A, B in S => A U B in S
I : A, B in S => A intersect B in S
\ : A, B in S with A contained in B => B\A in S
- : A in S => complement of A in X is in S
0 : S contains the empty set
1 : S contains the universe set X

We also define a new operation on subsets of X:


[points in P but not in A plus points in both Q and A]

Now Koenig defines 4 types of set systems:

a lattice   : properties U, I
an oval     : P,A,Q in S => |P|A|Q| in S
a ring      : properies U, I, \
an algebra  : properties U, I, -

The question is, how many lattices, ovals, rings, and algebras
are there on n labeled/unlabeled points?

(In fact one might consider any of the 2^7 combinations
of the above 7 properies!)

There are of course many sequences like these in the OEIS already,
but usually there is no precise definition (this should be corrected!)

For example: posets: A000112 (unlabeled), A001035 (labeled)
Boolean lattices: A005493
Set systems of various types, studied recently by

E.g.:
%I A102895
%S A102895 2,2,8,90,4542,2747402,151930948472
%N A102895 Number of ACI algebras or semilattices on n generators, with no identity element.
%C A102895 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
%C A102895 Or, number of families of subsets of {1, ..., n} that are closed under intersection and contain the empty set.

- this seems to count subsets with properties I, 0 in the labeled case

%I A102897
%S A102897 2,4,14,122,4960,2771104,151947502948
%N A102897 Number of ACI algebras (or semilattices) on n generators.
%C A102897 Also counts Horn functions on n variables, boolean functions whose set of truth assignments are closed under 'and', or equivalently, the boolean functions that can be written as a conjunction of Horn clauses, clauses with at most one negative literal.
%C A102897 Also, number of families of subsets of {1,...,n} that are closed under intersection (because we can throw in the universe, or take it out, without affecting anything else).
%C A102897 An ACI algebra or semilattice is a system with a single binary, idempotent, commutative and associative operation.
- this seems to count subsets with property I in the labeled case ?

Likewise A102896 seems to count subsets with properties I, 1 in the labeled case
and      A102894 seems to count subsets with properties I, 0, 1 in the labeled case

(see the full entries for more details)

Neil