On page 916 of A New Kind of Science, the question is addressed what integer functions can be used to produce all integers just from 1s (e.g. Plus can produce all positive integers, because 1=1, 2=1+1, 3=1+1+1 etc.). With the help of a function new in Mathematica 11 I have studied various classes of integer functions and created a tool-set for visualizing the data. For example the following image is showing which integers can be produced by
BitXor[#1, #2, #1 + 2 #2] &
using at most eight 1s and how - grey squares represent opening of a bracket, black closing of a bracket. Image showing which integers can be produced by
BitXor[#1, #2, #1 + 2 #2] &
using at most eight 1s and how - grey squares represent opening of a bracket, black closing of a bracket
The conjecture was made that the function
BitOr[2 #2,#1+#2]&
produces all positive integers but those of the form 16k and 16k+1, and the functions
{BitXor[BitXor[#1,#2]+#1,2 #2]&,
BitXor[#2,BitXor[#1,#2]+#1+#2]&,
BitXor[#1,#1+#2]&, BitXor[#1,
BitXor[#1,#2]+2 #2]&, BitXor[2 #1,#2]&,
BitXor[BitXor[#1,#2]+#1,2 #2]&,
BitXor[#2,BitXor[#1,#2]+#1+#2]&,
BitXor[#1,#2,#1+2 #2]&,
BitXor[#2,#1+2 #2]+#1&,
BitXor[#2,2 #1+#2]+#2&,
2 #1+#2&,
BitAnd[2 #2,#1+#2]+#1&,
BitAnd[2 #1,2 #2]+#2&, and
BitAnd[#1,#2]+#1+#2&, 2 #1+#2&, #1+2 #2&}
produce all positive odd integers. The Union of integers produced by the first mentioned function from at most 12 ones is as follows:
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,19,20,21,22,23,24,25,26,27,28,29,30,31,34,35,36,37,38,39,40,41,42,43,44,45,46,47,50,51,52,53,54,55,56,57,58,59,60,61,62,63,66,67,68,69,70,71,72,73,74,75,76,77,78,79,82,83,84,85,86,87,90,91,92,93,94,95,98,100,101,102,103,104,106,107,108,109,110,111,114,115,116,117,118,119,120,121,122,123,124,125,126,127,130,131,132,133,134,135,136,138,139,140,141,142,143,146,148,150,156,157,158,190,196,197,198,199,200,202,203,204,205,206,207,210,212,214,218,220,221,222,223,226,228,232,234,235,236,237,238,239,242,243,244,245,246,247,248,250,251,252,253,254,255,258,259,260,261,262,263,266,268,270,271,274,284,388,389,390,391,394,395,396,397,398,399,402,404,412,414,415,418,446,460,461,462,463,466,468,474,476,478,479,482,484,500,502,503,506,508,509,510,511,514,515,516,517,518,526,772,774,775,778,781,782,798,908,909,910,911,914,916,924,926,927,930,958,988,990,991,994,1020,1021,1022,1023,1026,1028,1540,1542,1543,1546,1550,1806,1822,1948,1950,1951,1954,1982,2044,2046,2047,2050,3598,4030,4094}.
What are the necessary and sufficient conditions for a function to produce all integers just from 1s remains to be an open question.