Floris P. van Doorn - cp's OEIS frontend

User: Floris P. van Doorn

Floris P. van Doorn has authored 4 sequences.

A318240 Triangle read by rows: T(n,k) = solution to Dagstuhl's Happy Diner Problem with n participants and tables of size at most k (n > k >= 2).

3, 3, 3, 5, 3, 3, 5, 4, 3, 3, 7, 4, 3, 3, 3, 7, 4, 3, 3, 3, 3, 9, 4, 4, 3, 3, 3, 3, 9, 6, 4, 4, 3, 3, 3, 3, 11, 6, 5, 4, 3, 3, 3, 3, 3, 11, 6, 5, 4, 3, 3, 3, 3, 3, 3, 13, 7, 5, 5, 4, 3, 3, 3, 3, 3, 3, 13, 7, 5, 5, 4, 4, 3, 3, 3, 3, 3, 3, 15, 7, 5, 5, 4, 4, 3

Offset: 3

Floris P. van Doorn, Aug 22 2018

There are n participants at a conference, which share meals together in a room with multiple tables. Each table seats at most k participants. T(n,k) is the smallest number of meals so that each participants can share at least one meal with every other participant.
There is no requirement on the number of tables, participants can have a meal together more than once, and not every table needs to be fully occupied.
T(1,k) = 0 and T(n,k) = 1 for 1 < n <= k. These trivial values are omitted in this sequence.
Since every participant can sit with at most (k-1) other participants, T(n,k) >= (n-1)/(k-1).
If A107431(n,k) * (k-1) = n*k - 1 then T(n * k, k) = A107431(n,k).
If A107431(n,k) * (k-1) = n*k - 2 then T(n * k, k) = A107431(n,k) + 1.

			The triangle begins as follows. The first entry is (n,k) = (3,2).
  3
  3 3
  5 3 3
  5 4 3 3
  7 4 3 3 3
  ...
T(4,2) = 3 from the table assignment { 12/34, 13/24, 14/23 }

Github, Dagstuhl's Happy Diner Problem

Column 3 gives A318241.

Cf. A107431.

A318241 Column 3 of array in A318240.

Original entry on oeis.org

0, 1, 1, 3, 3, 4, 4, 4, 4, 6, 6, 6, 7, 7, 7, 9, 9, 9, 10, 10, 10, 12, 12, 12, 13, 13, 13

Offset: 1

Floris P. van Doorn, Aug 25 2018

The next value a(28) is either 15 or 16.
a(6k+1) = a(6k+2) = a(6k+3) = 3k+1 for k >= 1. This follows from the solution to Kirkman's schoolgirl problem with n schoolgirls.
The values of a(6k), a(6k-1) and a(6k-2) are either 3k or 3k+1.

D. K. Ray-Chaudhuri and Richard M. Wilson, Solution of Kirkman's schoolgirl problem, in Proceedings of Symposia in Pure Mathematics, Volume 19, 1971.
Wikipedia, Kirkman's schoolgirl problem

Cf. A318240.

A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.

Original entry on oeis.org

0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9, 9, 10, 10, 9, 10, 10, 9, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 12, 11, 12, 12, 11, 12, 12, 12, 12, 13, 11, 12, 12, 12, 13, 13, 12, 13, 13, 12, 12, 13, 13, 14, 13, 13, 13, 14, 12, 13, 13, 13, 13, 14, 13, 14, 13, 12, 13, 14, 13, 14, 14, 14, 14, 15

Offset: 1

Floris P. van Doorn, Oct 15 2017

nonn

The machine has a cache which holds 1 integer and a memory which holds a list of integers.
The machine starts with a number 1 in cache and empty memory.
At every step, the machine can do one of three things:
  (1) write the number from cache to a new position in memory;
  (2) read any number from memory and put it in cache;
  (3) add any number from memory to the number in cache.
a(n) is the minimum number of steps needed to get the number n in cache.
Conjecture: reading from memory (operation 2) is never needed to get to a number in the minimal number of steps.
Additional conjectures and comments by Glen Whitney, Oct 12 2021: (Start)
Conjecture II: For each n, there is a minimal-length program for n that stores numbers in memory in increasing order.
Conjecture III: For each n, there is a minimal-length program such that the difference between successive numbers stored in memory is strictly increasing.
All three conjectures are empirically verified for all programs of length 23 or less, and all values of n up to 2326. However, note that if you are allowed to specify the set of numbers that must be stored in memory, then the first conjecture fails for memory {1,3,9,27,30,54} and conjecture II fails for {1,3,9,27,30,54,60}. (These sequences of numbers in memory are similar to addition chains, see A003313.) Hence, a proof of the first conjecture might need to involve showing that every n has a "good" sequence of numbers that can be stored in memory to produce n, avoiding the need to invoke the read operation. Conjecture III supplies one speculative possibility of a property that might fill the role of "good." A proof of any of these conjectures would tremendously speed up computation of a(n) as compared to brute force. (End)
One can add a useless read instruction after the first operation of writing the initial one in cache to memory. Therefore, there is always a program one step longer than optimal that performs a read. Thus, in a numerical search, the first sign one might observe that read operations can be helpful is a tie for shortest between a program that does read and one that doesn't, for some value of n. However, no such ties occur for program length 21 or less. - Glen Whitney, Oct 23 2021

			For n = 23 we need 10 steps to get 23 in cache:
   1. Write 1 to memory
   2. Add 1 to cache (cache contains 2)
   3. Write 2 to memory
   4. Add 2 to cache (cache contains 4)
   5. Add 2 to cache (cache contains 6)
   6. Add 1 to cache (cache contains 7)
   7. Write 7 to memory
   8. Add 7 to cache (cache contains 14)
   9. Add 7 to cache (cache contains 21)
  10. Add 2 to cache (cache contains 23)
There are several other essentially different 10-step programs that result in 23 in cache, but no 9-step programs. (If a program differs just by the order of a sequence of successive additions, it's not considered essentially different.) Note that for all n < 2326, all of the numbers that have an essentially unique minimal program that puts a maximal set of numbers in memory are of the form 2^k, 1+2^k, 3^k, or 1+3^k, except for 5, 809 and 1609:
For n = 809 we need 21 steps: (1) W1; (2) A1 => 2; (3) A1 => 3; (4) W3; (5) A3 => 6; (6) A3 => 9; (7) A1 => 10; (8) W10; (9) A10 => 20; (10) W20; (11) A20 => 40; (12) W40; (13) A40 => 80; (14) W80; (15) A80 => 160; (16) A80 => 240; (17) A3 => 243; (18) W243; (19) A243 => 486; (20) A243 => 729; (21) A80 => 809.
n = 1609 can be computed most efficiently in 23 steps. The contents of memory when 1609 is reached are {1,3,10,20,40,80,160,483}; the precise steps can be inferred from these memory contents.

Glen Whitney, Table of n, a(n) for n = 1..2326 (Terms 1..340 from Robert G. Wilson v)
Glen Whitney, C program to compute a(n) for small values of a(n)
Glen Whitney, Somewhat more efficient C program to compute a(n)
Index to sequences related to the complexity of n

Cf. A005245, A091333, A172005.

Cf. A003313 (addition chains; similar except read/write are "free").

PossibleNextStates[{n_, l_}] :=
Join[{#, l} & /@ l,
  If[! MemberQ[l, n], {{n, Sort@Append[l, n]}}, {}], {n + #, l} & /@ l]
states = {{1, {}}}; i = 0; c[1] = 0;
Do[states = Union @@ PossibleNextSteps /@ states; i++;
  If[! IntegerQ[c[#[[1]]]], c[#[[1]]] = i] & /@ states, {14}];
c /@ Range[88]

A165739 The number of palindromic numbers which are the product of a number and its reversal with 2n-1 digits.

Original entry on oeis.org

4, 3, 8, 13, 27, 49, 99, 180, 330, 567, 957, 1546, 2479, 3865

Offset: 1

Floris P. van Doorn, Sep 25 2009

Every palindromic numbers which is the product of a number and its reversal has an odd number of digits.

			a(1)=4 because there are 4 numbers matching the definition with one digit: 0*0=0; 1*1=1; 2*2=4; 3*3=9;
a(2)=3 because there are 3 numbers with three digits: 11*11=121; 12*21=252; 22*22=484;
a(3)=8 because there are 8 numbers with five digits: 101*101=10201; 111*111=12321; 121*121=14641; 102*201=20502; 112*211=23632; 122*221=26962; 202*202=40804; 212*212=44944;

Cf. A158642.

cp's OEIS Frontend

User: Floris P. van Doorn

A318240 Triangle read by rows: T(n,k) = solution to Dagstuhl's Happy Diner Problem with n participants and tables of size at most k (n > k >= 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A318241 Column 3 of array in A318240.

Views

Author

Keywords

Comments

Links

Crossrefs

A293771 Minimum number of steps needed to compute n using a machine that can read, write and add starting with the number 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A165739 The number of palindromic numbers which are the product of a number and its reversal with 2n-1 digits.

Views

Author

Keywords

Comments

Examples

Crossrefs