Message Boards Message Boards

GROUPS:

[WSS16] Representation of Integers in terms of 1s

Posted 3 years ago
1567 Views
|
0 Replies
|
3 Total Likes
|

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

im

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.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract